Sau hàng trăm năm, thành phố JOI đã trở thành phế tích. Nhà thám hiểm IOI-chan đang khám phá nơi từng có thư viện. Qua khảo sát, cô biết được rằng:

• Trên giá sách có \(N\) quyển sách, xếp thành một hàng từ trái sang phải.
• Các quyển sách được đánh số từ \(1\) đến \(N\), nhưng thứ tự trên giá không nhất thiết là thứ tự các số hiệu.
• Trong một thao tác, có thể lấy cùng lúc các quyển sách nằm liên tiếp trên giá.

Đáng tiếc, IOI-chan không tìm thấy những quyển sách cũ. Tuy nhiên, cô tìm được một cỗ máy từng quản lý các thao tác trên giá sách. Khi chỉ định một hoặc nhiều quyển sách bằng số hiệu và gửi truy vấn, máy trả về số thao tác ít nhất cần thực hiện để lấy chỉ những quyển sách được chỉ định khỏi giá.

IOI-chan muốn dùng các truy vấn để xác định thứ tự sách. Nếu đảo ngược thứ tự của toàn bộ \(N\) quyển sách, mọi câu trả lời của máy đều không đổi, nên cô không cần phân biệt thứ tự từ trái sang phải với thứ tự từ phải sang trái. Vì máy đã cũ, cô chỉ được gửi nhiều nhất \(20\,000\) truy vấn.

Hãy viết chương trình xác định thứ tự các quyển sách bằng nhiều nhất \(20\,000\) truy vấn. Có thể trả lời thứ tự theo một trong hai chiều.

Chi tiết cài đặt

Bạn cần nộp một tệp library.cpp, khai báo #include "library.h" và cài đặt hàm:

void Solve(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số quyển sách trên giá. Chương trình của bạn có thể gọi các hàm sau.

int Query(const std::vector<int>& M);

Hàm trả về số thao tác ít nhất để lấy chỉ những quyển sách được chỉ định. Vectơ M có kích thước \(N\). Với mỗi \(1\le i\le N\), M[i-1] = 1 nghĩa là chọn quyển sách số \(i\), còn M[i-1] = 0 nghĩa là không chọn.

• Nếu kích thước M khác \(N\), chương trình bị đánh giá Wrong Answer [1].
• Mọi phần tử phải bằng \(0\) hoặc \(1\), và phải có ít nhất một phần tử bằng \(1\). Nếu vi phạm một trong hai điều kiện này, chương trình bị đánh giá Wrong Answer [2].
• Nếu gọi Query quá \(20\,000\) lần, chương trình bị đánh giá Wrong Answer [3].

void Answer(const std::vector<int>& res);

Hàm này thông báo thứ tự sách. Vectơ res có kích thước \(N\); res[i-1] là số hiệu quyển sách ở vị trí thứ \(i\) từ trái sang phải. Có thể trả lời thứ tự đảo ngược.

• Nếu kích thước res khác \(N\), chương trình bị đánh giá Wrong Answer [4].
• Mỗi phần tử phải là số nguyên từ \(1\) đến \(N\), nếu không chương trình bị đánh giá Wrong Answer [5].
• Các phần tử phải đôi một khác nhau, nếu không chương trình bị đánh giá Wrong Answer [6].
• Khi Solve kết thúc, nếu số lần gọi Answer khác \(1\), chương trình bị đánh giá Wrong Answer [7].
• Nếu thứ tự được trả lời không phải thứ tự thật và cũng không phải thứ tự đảo ngược của nó, chương trình bị đánh giá Wrong Answer [8].

Lưu ý quan trọng

• Bạn có thể cài đặt thêm các hàm dùng nội bộ và sử dụng biến toàn cục.
• Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra luồng lỗi chuẩn.

Biên dịch và chạy thử

Trang web kỳ thi cung cấp gói tải xuống chứa trình chấm mẫu và mã nguồn mẫu. Đặt grader.cpp, library.cpp và library.h trong cùng thư mục rồi biên dịch bằng lệnh mẫu:

g++ -std=c++14 -O2 -o grader grader.cpp library.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào của trình chấm mẫu

• Dòng đầu chứa số nguyên \(N\), số quyển sách.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(A_i\), số hiệu quyển sách ở vị trí thứ \(i\) từ trái sang phải.

Dữ liệu ra của trình chấm mẫu

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

• Nếu câu trả lời đúng, ghi số lần gọi Query, chẳng hạn Accepted : 100..
• Nếu chương trình bị đánh giá sai, ghi loại lỗi, chẳng hạn Wrong Answer [1]..

Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le 1\,000\).
• \(1\le A_i\le N\) với \(1\le i\le N\).
• \(A_i\ne A_j\) với \(1\le i<j\le N\).

Phân nhóm

1. \(19\) điểm: \(N\le 200\)
2. \(81\) điểm: Không có

Ví dụ giao tiếp

5
4
2
5
3
1

Trình chấm gọi Solve(5). Trong lần gọi này, chương trình thực hiện:

Không cần phân biệt hai chiều của giá sách. Vì vậy, gọi Answer({1,3,5,2,4}) với thứ tự đảo ngược cũng được chấp nhận.

Nguồn

JOI 2017/2018 Spring Training Camp, Contest Day 4, đề tiếng Anh chính thức.