Hoán Vị Qua Phần Dư · canuc80k2804

Description

Khôi phục hoán vị ẩn của $1, \dots, n$ bằng truy vấn phần dư $p_{i}$ mod $p_{j}$ .

Trạng thái cần tìm được bộ tương tác chọn trước khi phiên bắt đầu và không thay đổi trong suốt phiên. Lời giải không được đọc trực tiếp trạng thái này; mọi thông tin chỉ đến từ các phản hồi hợp lệ của giao thức bên dưới.

Interaction

Đọc đúng một số $n$ . Truy vấn ? $i$ $j$ với $i$ khác $j$ ; đáp án ! $p_{1}, \dots, p_{n}$ . Flush sau mỗi dòng.

Bộ tương tác trả $p_{i}$ mod $p_{j}$ . Dòng đáp án phải chứa đúng $n$ giá trị.

Hoán vị đúng nhận AC, sai nhận WA. Sai cú pháp, sai chỉ số hoặc vượt $2 n$ truy vấn nhận lỗi giao thức. Khi nhận $- 1$ hoặc khi luồng vào kết thúc bất thường, chương trình phải dừng ngay. Mọi dòng truy vấn và đáp án đều phải được đẩy khỏi bộ đệm, chẳng hạn bằng endl hoặc cout.flush() trong C++.

Constraints

$1 \leq n \leq 1 0^{4}$ . Dãy ẩn là một hoán vị của $1, \dots, n$ và được dùng tối đa $2 n$ truy vấn.

Scoring

Subtask small - $50$ điểm: mười hidden session đầu dùng kích thước nhỏ để kiểm tra mô hình giao thức và các trường hợp biên cơ bản.
Subtask full - $50$ điểm: mười hidden session còn lại dùng toàn bộ giới hạn, gồm ít nhất hai session $upper - t ai l$ bổ sung cho nhau khi contract có nhiều đại lượng kích thước.
Mỗi hidden session có giá trị $5$ điểm. Một session chỉ được tính điểm khi toàn bộ cuộc hội thoại kết thúc với verdict AC.

Example interaction

Mẫu E01

Bộ tương tác -> Lời giải: 2
Lời giải -> Bộ tương tác: ? 1 2
Lời giải -> Bộ tương tác: ? 2 1
Bộ tương tác -> Lời giải: 0
Bộ tương tác -> Lời giải: 1
Lời giải -> Bộ tương tác: ! 2 1
Kết quả: AC

Giải thích: Trong phiên mẫu có hai vị trí. Hai truy vấn ngược chiều xác định ngay giá trị ở vị trí nhỏ hơn; vị trí còn lại bắt buộc chứa 2, nên hoán vị được khôi phục chính xác.

Ý tưởng: Giữ một vị trí ứng viên chứa giá trị lớn nhất chưa xác định; với vị trí mới hỏi cả hai chiều modulo, từ giá trị lớn hơn của hai phản hồi xác định giá trị ở vị trí nhỏ hơn và giữ vị trí lớn hơn làm ứng viên.
Tính đúng đắn: Ta duy trì đúng bất biến mô tả trong thuật toán sau mỗi phản hồi. Mỗi bước chỉ loại một khả năng khi phản hồi của bộ tương tác chứng minh khả năng đó không thể là đáp án; vì trạng thái ẩn không đổi trong phiên, bất biến được bảo toàn cho đến dòng kết luận. Khi thuật toán dừng, đối tượng còn lại hoặc các giá trị đã khôi phục là duy nhất phù hợp toàn bộ phản hồi, nên đáp án gửi đi là đúng.
Giới hạn truy vấn và độ phức tạp: 1 ≤ n ≤ 10000. Dãy ẩn là một hoán vị của 1..n và được dùng tối đa 2n truy vấn. Cài đặt dùng bộ nhớ tuyến tính theo kích thước trạng thái công khai, hoặc hằng số khi bài không có dãy công khai.