Đây là bài toán tương tác.
Ngay trước khi lễ hội tráng miệng khai mạc, bếp trưởng đang tỉ mỉ hoàn thiện món đặc trưng của cửa hàng — “千层幻彩慕斯”. Món tráng miệng này gồm $n$ miếng mousse có hương vị khác nhau, lần lượt được đánh số $0,1,\dots,n-1$.
Tuy nhiên, trong lúc luống cuống, người phụ bếp đã vô tình làm xáo trộn thứ tự sắp xếp các miếng mousse. Hiện chúng được xếp thành một hàng từ trái sang phải, tạo thành một hoán vị vị trí chưa biết $p=(p_0,p_1,\dots,p_{n-1})$, trong đó $p_i$ là số hiệu của miếng mousse ở vị trí thứ $i$.
Để xác định chính xác vị trí của từng miếng mousse, bạn có thể dùng máy kiểm tra món tráng miệng. Mỗi lần chọn ba vị trí khác nhau từng đôi một $x,y,z$, máy sẽ trả về tổng của số hiệu nhỏ nhất và số hiệu lớn nhất trong ba miếng mousse này:
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Tiếng chuông khai mạc sắp vang lên. Liệu bạn có thể khôi phục chính xác vị trí thực sự của từng miếng mousse bằng một số lần kiểm tra có giới hạn hay không?
Có một hoán vị $p$ độ dài $n$, gồm đúng các phần tử $0,1,\ldots,n-1$. Bạn không biết nội dung cụ thể của $p$.
Bạn có thể chọn ba chỉ số khác nhau từng đôi một $x,y,z$, và thư viện tương tác sẽ trả về
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Nhiệm vụ của bạn là khôi phục toàn bộ hoán vị. Giới hạn số lần truy vấn và cách tính điểm theo số lần truy vấn được mô tả bên dưới.
Chi tiết cài đặt
Thí sinh không cần và cũng không nên cài đặt hàm main. Tệp mã nguồn nộp lên phải chứa:
#include "mousse.h"Bạn cần cài đặt hai hàm sau:
void init(int c);
std::vector<int> mousse(int c, int n);- $c$ là số hiệu nhiệm vụ con; $c=0$ biểu thị ví dụ. Mỗi bộ kiểm thử chứa đúng một trường hợp dữ liệu. Với bộ kiểm thử đó, thư viện tương tác gọi
init(c)một lần, sau đó gọimousse(c,n)một lần. moussephải trả về một mảng độ dài $n$, trong đó phần tử thứ $i$ là $p_i$, với các chỉ số bắt đầu từ $0$.
Thí sinh có thể gọi hàm sau để thực hiện một truy vấn:
int query(int x, int y, int z);Phải thỏa mãn $0\le x,y,z < n$, và $x,y,z$ khác nhau từng đôi một. Hàm trả về $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.
Cách kiểm thử chương trình
Tệp đính kèm chứa mousse.h, thư viện tương tác cục bộ grader.cpp và chương trình mẫu template_mousse.cpp. Lưu chương trình của bạn thành mousse.cpp, rồi có thể chạy các lệnh sau trong thư mục của bài toán:
g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.inThư viện tương tác cục bộ đọc hoán vị ẩn từ đầu vào chuẩn; chương trình của thí sinh không được tự đọc dữ liệu này. Định dạng dữ liệu vào như sau:
- Dòng đầu tiên chứa hai số nguyên $c,n$.
- Dòng thứ hai chứa $p_0,p_1,\ldots,p_{n-1}$.
Nếu đáp án đúng, thư viện tương tác in ra Correct! và Max queries used: Q, trong đó $Q$ là số lần truy vấn của bộ kiểm thử đó; nếu đáp án sai, thư viện in ra Wrong answer.. Khi nhận truy vấn không hợp lệ hoặc vượt quá giới hạn số lần truy vấn, chương trình in thông báo lỗi ra luồng lỗi chuẩn rồi thoát. Bạn có thể thêm tham số -v để xem số lần truy vấn của bộ kiểm thử đó.
Ví dụ
Dữ liệu vào 1
0 10
0 2 9 1 5 8 3 7 6 4Dữ liệu ra 1
Correct!
Max queries used: 15Ghi chú
Ví dụ, khi gọi query(0,1,2), ba giá trị tương ứng là $0,2,9$, và hàm trả về $0+9=9$. Chương trình tham khảo sử dụng $15$ truy vấn cho trường hợp dữ liệu này. Nếu dùng chiến lược khác, số lần truy vấn của bạn có thể khác.
Giới hạn
Với mọi dữ liệu kiểm thử, $n\in\{10,100,10^5\}$, và $p$ là một hoán vị của $0\sim n-1$. Mỗi bộ kiểm thử chứa đúng một trường hợp dữ liệu.
| Số hiệu nhiệm vụ con | Điểm | $n =$ | $Q_{\max} = $ | Tính chất đặc biệt |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | Không có |
| $2$ | $5$ | $100$ | $10000$ | Không có |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | Không có |
Trong ví dụ, $c=0$, $n=10$, và giới hạn số lần truy vấn là $1000$.
Nhiệm vụ con
Lưu ý:
- Thư viện tương tác không có tính thích ứng. Hoán vị của mỗi bộ kiểm thử đã được xác định trước khi gọi chương trình của thí sinh và không thay đổi theo các truy vấn.
- Thí sinh không được lấy hoán vị ẩn bằng cách đọc đầu vào chuẩn hoặc bằng các cách không hợp lệ khác. Cách cài đặt thư viện tương tác dùng trong chấm thi chính thức có thể khác với thư viện tương tác cục bộ.
Nếu trong một bộ kiểm thử, mousse trả về đáp án sai, các tham số của query không hợp lệ, hoặc số lần truy vấn vượt quá $Q_{\max}$ của nhiệm vụ con đó, hệ số điểm của bộ kiểm thử này bằng $0$.
Trong các nhiệm vụ con $1,2$, bạn chỉ nhận được toàn bộ điểm của nhiệm vụ con nếu trả lời đúng tất cả các bộ kiểm thử.
Với các nhiệm vụ con $3,4$, nếu bất kỳ bộ kiểm thử nào có hệ số điểm bằng $0$, nhiệm vụ con đó được $0$ điểm. Nếu không, gọi $Q$ là số lần truy vấn lớn nhất trong tất cả các bộ kiểm thử của nhiệm vụ con đó. Hệ số điểm $f(Q)$ được xác định theo bảng sau:
| Số lần truy vấn $Q_i$ | Hệ số điểm $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
Nếu $Q\le 99970$, thì $f(Q)=100\%$. Nếu $Q$ nằm giữa hai dòng liền kề $(Q_i,f_i)$ và $(Q_{i+1},f_{i+1})$ trong bảng, thì:
$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$
Điểm của nhiệm vụ con $3$ là $30f(Q)$, và điểm của nhiệm vụ con $4$ là $60f(Q)$. Điểm cuối cùng được làm tròn đến $3$ chữ số sau dấu thập phân.
Giới hạn thời gian: $10\ \mathrm{s}$.
Giới hạn bộ nhớ: $512\ \mathrm{MiB}$.