Dù những ngày làm kẻ trộm tranh đã lùi xa, bạn vẫn không mất đi niềm yêu thích nghệ thuật đương đại. Đáng tiếc là gần đây bạn quá bận chuẩn bị cho BOI nên không còn nắm được thứ hạng theo giá trị của \(N\) bộ sưu tập nghệ thuật đương đại nổi tiếng nhất, được đánh số từ \(1\) đến \(N\). Hỏi thẳng người khác thì thật đáng ngượng, vì vậy bạn phải tìm cách khác: đăng các bảng xếp hạng ẩn danh trên mạng.

Bạn sẽ lặp lại việc sau: đoán thứ hạng của \(N\) bộ sưu tập theo giá trị, từ đắt nhất đến rẻ nhất, đăng bảng xếp hạng lên một trang web, rồi chờ chủ các bộ sưu tập phàn nàn trong phần bình luận. Vì không muốn đọc từng bình luận, bạn chỉ đếm tổng số lời phàn nàn nhận được. May thay, hành vi của các chủ sở hữu rất nhất quán: mỗi người phàn nàn đúng một lần cho mỗi bộ sưu tập bị bạn xếp cao hơn bộ sưu tập của họ dù trong thứ hạng thật thì không phải vậy. Không ai phàn nàn về những bộ sưu tập bị bạn xếp thấp hơn bộ sưu tập của họ một cách sai lầm. Giá trị của các bộ sưu tập đôi một khác nhau.

“Độc giả còn thích: 13 ứng dụng GÂY SỐC của thuật toán Dijkstra mà các nhà khoa học máy tính không muốn bạn biết!”

Tuy nhiên, mỗi lần đăng bảng xếp hạng đều có nguy cơ làm lộ danh tính của bạn — chắc chắn là do văn phong đặc trưng, chứ không phải vì bạn hay vô tình ký tên mình vào bài viết. Vì vậy, bạn chỉ muốn đăng tối đa \(4\,000\) bảng xếp hạng dự đoán trước khi tìm ra thứ hạng chính xác. Hãy viết chương trình giúp bạn quyết định nên đăng những bảng xếp hạng nào.

Giao tiếp

Đây là bài tương tác thông qua hàm. Bạn phải cài đặt hàm sau; với mỗi bộ dữ liệu, trình chấm gọi hàm đúng một lần, trong đó \(N\) là số bộ sưu tập:

void solve(int N);

Trong solve, bạn được sử dụng các hàm do trình chấm cung cấp:

int publish(std::vector<int> R);
void answer(std::vector<int> R);

• publish(R) đăng bảng xếp hạng \(R\) lên trang web. \(R\) phải là một hoán vị của các số từ \(1\) đến \(N\), với những bộ sưu tập mà bạn đoán là đắt hơn đứng trước. Hàm trả về số lời phàn nàn nhận được. Bạn được gọi hàm này tối đa \(4\,000\) lần trong mỗi bộ dữ liệu.
• answer(R) thông báo rằng bạn đã tìm được thứ hạng chính xác \(R\), theo cùng định dạng với publish. Bạn phải gọi answer đúng một lần; chương trình sẽ tự động bị kết thúc ngay sau đó.

Nếu một lời gọi không thỏa mãn các điều kiện trên, chương trình bị kết thúc ngay và nhận kết quả Not correct cho bộ dữ liệu tương ứng. Bạn không được ghi ra đầu ra chuẩn hoặc đọc từ đầu vào chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.

Mã nguồn phải chứa #include "art.h". Bạn cài đặt solve, không viết hàm main.

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

Gói đính kèm của bài trên CMS chính thức có art.h, trình chấm mẫu sample_grader.cpp và chương trình mẫu art_sample.cpp. Có thể liên kết bài làm với trình chấm mẫu để chạy thử; hướng dẫn nằm trong sample_grader.cpp. Chẳng hạn, đặt art.cpp, art.h và sample_grader.cpp trong cùng thư mục rồi chạy:

g++ -std=c++17 sample_grader.cpp art.cpp
./a.out

Trình chấm mẫu đọc hai dòng từ đầu vào chuẩn. Dòng đầu chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, là thứ hạng chính xác của các bộ sưu tập, theo cùng định dạng với publish và answer. Sau đó, trình chấm gọi solve(N) và ghi nhật ký tất cả các lời gọi hàm trình chấm ra đầu ra chuẩn. Khi kết thúc, nó in một trong các thông báo sau:

• Invalid input.: dữ liệu nhập cho trình chấm không đúng định dạng trên.
• Invalid published ranking.: gọi publish với tham số không hợp lệ.
• Too many published rankings.: gọi publish quá \(4\,000\) lần.
• No answer.: hàm solve kết thúc mà chưa gọi answer.
• Wrong answer.: gọi answer với thứ hạng không đúng.
• Correct: p published ranking(s).: gọi answer với thứ hạng đúng sau \(p\) lần gọi publish.

Các thông báo trên giữ nguyên cách viết trong PDF chính thức. Trình chấm thật chỉ in Not correct khi gặp bất kỳ lỗi nào ở trên, hoặc Correct. Cả trình chấm mẫu lẫn trình chấm thật đều tự động kết thúc chương trình khi có lỗi hoặc sau khi bạn gọi answer. Việc đọc và ghi các luồng chuẩn ở phần chạy thử do trình chấm mẫu thực hiện.

Ràng buộc

• \(2\le N\le4\,000\).
• Giới hạn thời gian: \(3\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(5\) điểm: \(N\le6\).
2. \(15\) điểm: \(N\le40\).
3. \(15\) điểm: \(N\le250\).
4. \(15\) điểm: \(N\le444\).
5. \(20\) điểm: \(N\le2\,000\).
6. \(30\) điểm: không có ràng buộc thêm.

Ví dụ giao tiếp

Xét \(N=3\), trong đó bộ sưu tập \(1\) đắt nhất, tiếp theo là bộ sưu tập \(3\), còn bộ sưu tập \(2\) rẻ nhất. Trước tiên, trình chấm gọi solve(3). Một quá trình giao tiếp có thể diễn ra như sau; mũi tên chỉ giá trị trả về:

publish({1, 2, 3}) -> 1
publish({2, 3, 1}) -> 3
answer({1, 3, 2})

Lần đăng đầu tiên nhận một lời phàn nàn từ chủ bộ sưu tập \(3\). Lần thứ hai nhận hai lời phàn nàn từ chủ bộ sưu tập \(1\) và một lời phàn nàn từ chủ bộ sưu tập \(3\). Sau đó, bạn tin rằng đã tìm được thứ hạng chính xác và gọi answer({1, 3, 2}); câu trả lời đúng và được chấp nhận.