Aidos đã nghĩ ra một câu đố và thách thức Temirulan giải nó. Anh ấy đã chọn một dãy $a$ gồm $n$ số nguyên không âm phân biệt được đánh số từ 1 đến $n$: $a_1, a_2, ..., a_n$.
Temirulan có thể đặt hai loại câu hỏi:
ask— Tiết lộ số tại vị trí $i$ của dãy đã cho.get_pairwise_xor— Với dãy các số nguyên phân biệt đã cho: $i_1, i_2, ..., i_k$, lấy tập hợp các giá trị XOR từng đôi một của các phần tử trong dãy $a$ tại các chỉ số $i_1, i_2, ..., i_k$, $\{a_{i_x} \oplus a_{i_y} \mid 1 \leq x, y \leq k\}$.
Ví dụ, giả sử Aidos đã chọn dãy $[1, 5, 6, 3]$. Khi đó với câu hỏi ask(2), Aidos sẽ trả lời bằng số 5 và với câu hỏi get_pairwise_xor({3, 4}), Aidos sẽ trả lời bằng dãy $[0, 0, 5, 5]$, vì:
- $a_3 \oplus a_4 = 6 \oplus 3 = 5$
- $a_4 \oplus a_3 = 3 \oplus 6 = 5$
- $a_3 \oplus a_3 = 6 \oplus 6 = 0$
- $a_4 \oplus a_4 = 3 \oplus 3 = 0$.
Temirulan đã không thể giải được câu đố và nhiệm vụ của bạn là giúp anh ấy. Hãy tìm dãy số ẩn bằng cách sử dụng các câu hỏi được mô tả ở trên.
Dữ liệu vào
BÀI LÀM CỦA BẠN KHÔNG ĐƯỢC ĐỌC TỪ DỮ LIỆU VÀO TIÊU CHUẨN, GHI RA DỮ LIỆU RA TIÊU CHUẨN HOẶC TƯƠNG TÁC VỚI BẤT KỲ TỆP TIN NÀO KHÁC.
Nhiệm vụ của bạn là cài đặt hàm sau: int[] guess(int n)
- $n$: độ dài của dãy số ẩn.
- Hàm này được gọi chính xác một lần cho mỗi bộ kiểm thử.
- Hàm phải trả về dãy số ẩn theo đúng thứ tự.
Hàm của bạn có thể gọi các hàm sau:
int ask(int i)- $i$: chỉ số của số trong dãy, $1 \leq i \leq n$.
- Hàm trả về số thứ $i$ của dãy số ẩn.
int[] get_pairwise_xor(int[] pos)- $pos$: danh sách các chỉ số không rỗng của dãy.
- Tất cả các phần tử trong $pos$ phải là các số nguyên phân biệt.
- Gọi $k$ là số lượng phần tử trong $pos$. Khi đó $1 \leq pos_i \leq n$ với mỗi $1 \leq i \leq k$.
- Hàm trả về danh sách đã sắp xếp gồm $k^2$ phần tử: tập hợp các giá trị XOR từng đôi một, $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \leq x, y \leq k\}$.
Bạn có thể gọi cả hai hàm không quá 200 lần tổng cộng cho mỗi bộ kiểm thử. Nếu bất kỳ điều kiện nào ở trên bị vi phạm, chương trình của bạn sẽ nhận kết quả Wrong Answer. Nếu không, chương trình của bạn sẽ nhận kết quả Accepted và điểm số của bạn được tính dựa trên tổng số lần gọi các hàm ask và get_pairwise_xor (Tham khảo phần "Nhiệm vụ con").
Giới hạn
- $2 \leq n \leq 100$
- $0 \leq a_i \leq 10^9$ với mỗi $1 \leq i \leq n$.
Trong bài toán này, trình chấm KHÔNG thích nghi. Điều này có nghĩa là dãy $a$ được cố định ngay từ đầu khi chạy trình chấm và không phụ thuộc vào các lời gọi từ chương trình của bạn.
Nhiệm vụ con
- (6 điểm) $n \leq 4$
- (94 điểm) Không có ràng buộc bổ sung. Đối với nhiệm vụ con này, điểm số của bạn được tính như sau. Gọi $q$ là tổng số lần gọi các hàm
askvàget_pairwise_xor.- Nếu $q \leq 15$, điểm của bạn là 94.
- Nếu $15 < q \leq 40$, điểm của bạn là $84 - 2(q - 16)$.
- Nếu $40 < q \leq 50$, điểm của bạn là 35.
- Nếu không, điểm của bạn là 0.
Lưu ý rằng điểm số của bạn cho mỗi nhiệm vụ con là điểm số tối thiểu trong tất cả các kết quả trên các bộ kiểm thử của nhiệm vụ con tương ứng.
Ghi chú
Phép toán xor là phép toán OR loại trừ trên bit (bitwise exclusive OR).
Giả sử dãy số ẩn $a$ là $[1, 5, 6, 3]$. Trình chấm gọi hàm. Ví dụ về tương tác như sau:
| Lời gọi | Kết quả |
|---|---|
ask(2) |
5 |
get_pairwise_xor({1, 2, 3}) |
$\{0, 0, 0, 3, 3, 4, 4, 7, 7\}$ |
ask(3) |
6 |
get_pairwise_xor({4, 2}) |
$\{0, 0, 6, 6\}$ |
get_pairwise_xor({2}) |
$\{0\}$ |
Trình chấm mẫu đọc dữ liệu vào theo định dạng sau: Dòng 1: $n$ Dòng 2: $a_1, a_2, ..., a_n$
BẠN CÓ THỂ TẢI XUỐNG xoractive.zip trong hệ thống, chứa các ví dụ cho các ngôn ngữ Java, C++11, FPC, Python 2.
Tất cả các ví dụ về việc gọi hàm có thể được tìm thấy ở trên. Đối với Python 2, bạn phải cài đặt hàm def guess(n, interactor), trong đó interactor là một thực thể của lớp đang được kiểm thử. Các hàm ask và get_pairwise_xor là các phương thức của lớp này.
xoractive.zip chứa các ví dụ về lời giải cho mỗi ngôn ngữ.
Đối với các lời giải bằng ngôn ngữ Java, tên tệp và tên lớp phải được đặt là Xoractive.java và Xoractive tương ứng.
Đối với các lời giải bằng ngôn ngữ Pascal, tệp phải được đặt tên là xoractive.pas.