Trong khi lạc đường từ ký túc xá đến Trung tâm UQ, bạn tình cờ tìm thấy lối vào một hệ thống hang động bí mật nằm sâu dưới trường. Lối vào bị chặn bởi một hệ thống an ninh gồm \(N\) cánh cửa liên tiếp, cửa này nằm sau cửa kia, và \(N\) công tắc, mỗi công tắc nối với một cánh cửa khác nhau.

Các cửa được đánh số từ \(0\) đến \(N-1\) theo thứ tự, cửa \(0\) gần bạn nhất. Các công tắc cũng được đánh số từ \(0\) đến \(N-1\), nhưng bạn không biết công tắc nào nối với cửa nào.

Tất cả công tắc đều nằm ở lối vào hang. Mỗi công tắc có thể ở vị trí trên hoặc dưới. Với mỗi công tắc, chỉ một vị trí là đúng: ở vị trí đúng, cửa tương ứng mở; ở vị trí sai, cửa tương ứng đóng. Vị trí đúng có thể khác nhau giữa các công tắc và bạn chưa biết chúng.

Bạn có thể đặt các công tắc theo bất kỳ tổ hợp nào, rồi đi vào hang để xem cửa đầu tiên bị đóng. Các cửa không trong suốt: sau khi gặp cửa đầu tiên bị đóng, bạn không thể nhìn thấy bất kỳ cửa nào phía sau nó.

Bạn chỉ có thời gian thử tối đa \(70\,000\) tổ hợp. Hãy xác định vị trí đúng của từng công tắc và cửa mà từng công tắc nối tới.

Cài đặt

Nộp một tệp cài đặt hàm C/C++ sau và dùng #include "cave.h":

void exploreCave(int N);

Trình chấm cung cấp hai hàm sau để chương trình của bạn gọi:

int tryCombination(int S[]);
void answer(int S[], int D[]);

Dữ liệu vào

Tham số N của exploreCave là số cửa và số công tắc. Hàm này phải sử dụng tryCombination để xác định vị trí đúng và kết nối của từng công tắc, rồi kết thúc bằng cách gọi answer.

Trong tryCombination(S), S là mảng độ dài \(N\) mô tả một tổ hợp. S[i] là vị trí của công tắc \(i\): \(0\) là trên, \(1\) là dưới. Hàm trả về chỉ số cửa đầu tiên bị đóng, hoặc \(-1\) nếu tất cả cửa đều mở. Mỗi lời gọi chạy trong thời gian \(O(N)\), tức thời gian chạy trong trường hợp xấu nhất tỷ lệ với \(N\). Bạn được gọi hàm này nhiều nhất \(70\,000\) lần.

Dữ liệu ra

Khi đã xác định được đáp án, gọi answer(S, D). Hai mảng đều có độ dài \(N\). S[i] là vị trí đúng của công tắc \(i\), theo quy ước \(0\) là trên và \(1\) là dưới. D[i] là chỉ số cửa nối với công tắc \(i\).

Hàm answer không trả quyền điều khiển về chương trình của bạn; nó khiến chương trình kết thúc.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 32 MiB.
• \(1 \le N \le 5\,000\).
• Có tối đa \(70\,000\) lời gọi tryCombination.

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp cave.in theo định dạng:

• Dòng 1: N.
• Dòng 2: S[0] S[1] ... S[N-1].
• Dòng 3: D[0] D[1] ... D[N-1].

Ở đây S[i] là vị trí đúng của công tắc \(i\), và D[i] là cửa nối với công tắc \(i\). Những thông tin này dùng để thiết lập trình chấm mẫu; hàm exploreCave nhận tham số N và tìm hiểu hệ thống qua các lời gọi tương tác.

Ví dụ

4
1 1 1 0
3 1 0 2

answer([1, 1, 1, 0], [3, 1, 0, 2])