Một hoán vị ẩn \(p_0,p_1,\ldots,p_{N-1}\) của \(0,\ldots,N-1\) được cố định trước khi chương trình chạy. Bạn có thể hỏi \(p_i\mathbin{\mathrm{XOR}}p_j\) cho hai chỉ số tùy ý.

Hai hoán vị \(a,p\) được gọi là không thể phân biệt nếu \(a_i\mathbin{\mathrm{XOR}}a_j=p_i\mathbin{\mathrm{XOR}}p_j\) với mọi cặp chỉ số. Hãy tìm hoán vị nhỏ nhất theo thứ tự từ điển trong lớp không thể phân biệt với \(p\). Hoán vị \(x\) nhỏ hơn hoán vị \(y\) theo thứ tự từ điển nếu tại vị trí đầu tiên mà chúng khác nhau, phần tử của \(x\) nhỏ hơn phần tử của \(y\).

Giao diện thư viện

Submission C++ phải include xorting.h và cài đặt:

std::vector<int> solve(int N);

Grader cung cấp:

int get_xor(int i, int j);

solve được gọi đúng \(T\) lần. Mỗi lần phải trả hoán vị nhỏ nhất theo thứ tự từ điển. get_xor(i,j) trả \(p_i\mathbin{\mathrm{XOR}}p_j\) trong \(O(1)\); cả hai chỉ số phải thuộc \([0,N-1]\). Giới hạn truy vấn \(Q_i\) của mỗi lần gọi không được truyền cho submission.

Dữ liệu vào

Submission không đọc standard input. Sample grader đọc \(T\), loại giới hạn truy vấn, rồi từng hoán vị ẩn.

Dữ liệu ra

Submission không ghi standard output. Kết quả được trả từ solve.

Ràng buộc

• \(1\le N_i\le2^{20}\).
• \(1\le T\le2^{10}\).
• \(T\cdot\max_i N_i\le2^{25}\).
• Mỗi lần gọi được dùng \(Q_i=N_i\) hoặc \(Q_i=N_i^2\) tùy phân nhóm.

Phân nhóm

1. \(7\) điểm: \(N_i\le2^3\), \(T\le2^{10}\), \(Q_i=N_i^2\).
2. \(18\) điểm: \(N_i\le2^7\), \(T\le2^5\), \(Q_i=N_i^2\).
3. \(5\) điểm: \(N_i\le2^{11}\), \(T\le2^5\), \(Q_i=N_i^2\).
4. \(5\) điểm: \(N_i\le2^{11}\), \(T\le2^5\), \(Q_i=N_i\).
5. \(5\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\) và \(N_i\) là lũy thừa của \(2\).
6. \(5\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\) và \(N_i\) lẻ.
7. \(30\) điểm: \(N_i\le2^{18}\), \(T\le2^5\), \(Q_i=N_i\).
8. \(25\) điểm: \(N_i\le2^{20}\), \(T\le2^5\), \(Q_i=N_i\).

Ví dụ

Nếu hoán vị ẩn là [2,0,1,3], sáu truy vấn giữa các cặp chỉ số cho phép trả về [0,2,3,1], là hoán vị nhỏ nhất không thể phân biệt. Với \(N=1\), kết quả duy nhất là [0].

Nguồn

EJOI 2026 - Ngày 1, XORting.

Đề bài EJOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).