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

• Thư viện của thành phố JOI có một giá sách nằm ngang, gồm \(N\) vị trí đặt sách trên một hàng, đánh số từ \(0\) đến \(N-1\) từ trái sang phải. Mỗi vị trí đặt được đúng một quyển sách.
• Trên giá có \(N\) quyển sách, đánh số từ \(0\) đến \(N-1\).
• Một cách sắp xếp là một cách đặt toàn bộ \(N\) quyển sách vào \(N\) vị trí.
• Có một cách sắp xếp đúng: tại vị trí \(i\) (\(0\le i\le N-1\)) đặt quyển sách \(B_i\). Các giá trị \(B_i\) đôi một khác nhau.

Vị trí của các quyển sách thường bị thay đổi. Người ta biết rằng thư viện đưa sách trở lại cách sắp xếp đúng bằng cách lặp lại thao tác sau:

Gọi \(x\) là quyển sách nằm ngoài cùng bên trái trong số các quyển đang không ở đúng vị trí. Gọi \(y\) là quyển sách hiện đang nằm tại vị trí mà quyển \(x\) phải nằm trong cách sắp xếp đúng. Hoán đổi vị trí của hai quyển \(x,y\).

IOI-chan tìm thấy những quyển sách cũ nhưng không xác định được cách sắp xếp đúng. Tuy nhiên, cô tìm thấy một chiếc máy cũ từng quản lý các thao tác trên giá sách. Khi gửi một cách sắp xếp \(N\) quyển sách cho máy, máy trả về số thao tác cần thực hiện để đưa toàn bộ sách từ cách sắp xếp đó về cách sắp xếp đúng. IOI-chan muốn xác định cách sắp xếp đúng bằng cách gửi các truy vấn cho máy. Vì máy đã cũ, cô chỉ được gửi nhiều nhất \(5\,000\) truy vấn.

Hãy viết chương trình nhận thông tin về giá sách và xác định cách sắp xếp đúng bằng không quá \(5\,000\) truy vấn.

Chi tiết cài đặt

Nộp một tệp library3.cpp, sử dụng chỉ thị #include "library3.h" và cài đặt hàm:

void solve(int N);

Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử. Tham số N là số quyển sách.

Trong library3.cpp, bạn có thể gọi hai hàm sau:

int query(std::vector<int> a);
void answer(std::vector<int> b);

Hàm query gửi một truy vấn cho máy. Tham số a là mảng độ dài \(N\), mô tả cách sắp xếp: quyển sách a[i] được đặt tại vị trí \(i\) (\(0\le i\le N-1\)). Giá trị trả về là số thao tác cần thực hiện để đưa toàn bộ sách từ cách sắp xếp đã gửi về cách sắp xếp đúng.

Hàm answer báo cáo cách sắp xếp đúng. Tham số b là mảng độ dài \(N\), trong đó quyển sách b[i] được đặt tại vị trí \(i\) (\(0\le i\le N-1\)).

Các yêu cầu và trường hợp bị chấm sai:

Như vậy, phải gọi answer đúng một lần. Chương trình có thể định nghĩa các hàm phụ trợ và 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ỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

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

Gói tệp hỗ trợ của bài chứa trình chấm mẫu và mã nguồn mẫu. Trình chấm mẫu là tệp grader.cpp. Đặt grader.cpp, library3.cpp và library3.h trong cùng thư mục, rồi biên dịch bằng:

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

Hoặc chạy tệp compile.sh trong gói hỗ trợ. Khi 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

Định dạng đầu vào của trình chấm mẫu:

N
B_0 B_1 ... B_{N-1}

\(B_i\) (\(0\le i\le N-1\)) là số hiệu quyển sách tại vị trí \(i\) trong cách sắp xếp đúng.

Dữ liệu ra

Trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn và đầu ra lỗi chuẩn:

• Nếu chương trình đúng, báo số lần gọi query, chẳng hạn Accepted: 3000.
• Nếu chương trình bị chấm sai, báo loại lỗi, chẳng hạn Wrong Answer [3].

Nếu chương trình đồng thời thỏa mãn nhiều điều kiện bị chấm sai, trình chấm mẫu chỉ báo một loại lỗi.

Ràng buộc

• \(2\le N\le 500\).
• \(0\le B_i\le N-1\) với \(0\le i\le N-1\).
• \(B_i\ne B_j\) với \(0\le i<j\le N-1\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

Ví dụ

4
2 0 3 1

Nguồn

JOI Open Contest 2024, bài Library 3, tác giả Sora Todaka.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.