Long có một dãy số nguyên không âm ~a = a_1, a_2, \ldots, a_n~ (~a_i \leq 10^9, \forall i, 1\leq i \leq n~) và muốn tìm ra một cặp ~(i, j)~, ~1 \leq i < j \leq n~, sao cho ~a_i \wedge a_j~ lớn nhất có thể. Ở đây ~\wedge~ là phép toán xor, hay còn gọi là phép hoặc triệt tiêu. Dữ liệu đảm bảo cặp ~(i, j)~ tối ưu là duy nhất.
Vốn tính lập dị, tuy Long muốn được giúp nhưng lại không muốn tiết lộ dãy ~a~. Thay vào đó, bạn có thể trao đổi với Long bằng các hàm sau:
int get_n()
: trả về số phần tử của dãy ~a~;int max_xor(vector<int> &I, vector<int> &J)
(hoặcint max_xor(int[] I, int[] J)
đối với Java): trả về ~\max_{i \in I, j \in J} a_i \wedge a_j~ với ~I~ và ~J~ là hai tập con không giao nhau của tập ~\{1, 2, \ldots, n\}~;void answer(int i, int j)
: hàm này nhận vào hai tham số ~i~, ~j~ là câu trả lời cho Long.
Long sẽ trả lời không quá 33 câu hỏi dạng max_xor(I, J)
. Nếu bạn hỏi quá nhiều, hỏi với ~I~ và ~J~ không phải tập con của ~\{1, 2, \ldots, n\}~ hoặc hỏi với ~I~ và ~J~ có phần tử chung thì bài của bạn sẽ bị chấm sai.
Để sử dụng các hàm trên, với C++ bạn cần khai báo #include"MXORLIB.h"
ở đầu chương trình, sau đó các hàm đó có thể được gọi ở bất kỳ đâu trong chương trình của bạn. Xem file MXORLIB.h
và MXOR.cpp
trong mục đính kèm để hiểu rõ hơn cách tương tác. Lưu ý đây là thư viện ví dụ, có thể khác với thư viện dùng để chấm bài. Trình chấm đảm bảo rằng nếu chương trình của bạn biên dịch được với thư viện ví dụ thì cũng biên dịch được trên hệ thống (để MXORLIB.h
và chương trình của bạn vào cùng một thư mục rồi biên dịch như bình thường).
Đối với Java, hệ thống cung cấp sẵn một class tên là MXORLIB
và bạn không cần phải khai báo
gì thêm. Các hàm trên được để static, thí sinh gọi MXORLIB.get_n()
, MXORLIB.max_xor(I, J)
,
MXORLIB.answer(i, j)
để tương tác.
Các file mẫu có thể lấy ở đây.
Sample
Dãy ~a~ ban đầu là {4 3 1 2}
Gọi hàm | Giá trị trả về |
---|---|
get_n() |
4 |
max_xor({1}, {2, 3}) |
7 |
answer(1, 2) |
Kết thúc chương trình. Bạn đã trả lời đúng và chương trình đạt điểm của ví dụ này. |
Giới hạn
- Subtask 1 (16% điểm): ~n \leq 17~
- Subtask 2 (36% điểm): ~17 < n \leq 10^4~
- Subtask 3 (48% điểm): ~10^4 < n \leq 10^5~
Comments