Olympic Sinh Viên 2020 - Siêu cúp - Phép XOR

View as PDF

Submit solution

Points: 1.30 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem source:
Olympic Sinh Viên
Problem type
Allowed languages
C++, Java

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ặc int 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.hMXOR.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

Please read the guidelines before commenting.


There are no comments at the moment.