JOI-kun là một thợ làm bánh chuyên nghiệp, chuyên làm bánh dango Nhật Bản. Cửa hàng của cậu sử dụng \(N\) màu bánh, được đánh số từ \(1\) đến \(N\).

Một xiên dango đẹp là món bánh nổi tiếng của cửa hàng: xiên này gồm \(N\) chiếc bánh có màu đôi một khác nhau.

Với mỗi màu, JOI-kun có \(M\) chiếc bánh. Như vậy, cậu có tổng cộng \(N\times M\) chiếc bánh, được đánh số từ \(1\) đến \(N\times M\). Cậu muốn dùng toàn bộ số bánh này cùng \(M\) que xiên để làm \(M\) xiên dango đẹp.

Để tránh nhầm màu, JOI-kun sử dụng một máy kiểm tra dango. Khi nhận danh sách chỉ số của một số chiếc bánh, máy trả về số xiên dango đẹp lớn nhất có thể làm từ những chiếc bánh đó, giả sử có đủ que xiên.

JOI-kun muốn dùng máy kiểm tra để chia \(N\times M\) chiếc bánh thành \(M\) nhóm, mỗi nhóm gồm \(N\) chiếc bánh và chứa đúng một chiếc bánh của mỗi màu. Hãy cài đặt chiến lược thực hiện việc chia nhóm này với không quá \(50\,000\) lần sử dụng máy kiểm tra.

Chi tiết cài đặt

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

void Solve(int N, int M);

Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử. N là số màu bánh và M là số xiên dango đẹp cần làm.

Chương trình có thể gọi hai hàm sau do trình chấm cung cấp:

int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);

Query(x) gửi danh sách chỉ số bánh x tới máy kiểm tra. Giá trị trả về là số xiên dango đẹp lớn nhất có thể làm từ những chiếc bánh trong x, khi có đủ que xiên. Mỗi phần tử của x phải nằm trong đoạn \([1,N\times M]\), các phần tử phải đôi một khác nhau, và tổng số lần gọi Query không được vượt quá \(50\,000\). Danh sách rỗng được phép; khi đó giá trị trả về bằng \(0\).

Answer(a) thông báo một nhóm bánh dùng để làm một xiên dango đẹp. Danh sách a phải có đúng \(N\) phần tử thuộc đoạn \([1,N\times M]\) và chứa đúng một chiếc bánh của mỗi màu. Mỗi chỉ số bánh chỉ được xuất hiện một lần trong toàn bộ các lời gọi Answer, kể cả trong cùng một lời gọi. Khi Solve kết thúc, Answer phải đã được gọi đúng \(M\) lần.

Các trường hợp bị chấm sai:

Lưu ý

Chương trình được đị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ợ trong phần đính kèm chứa trình chấm mẫu grader.cpp, tệp tiêu đề dango3.h, mã nguồn mẫu dango3.cpp và các tệp đầu vào mẫu. Đặt ba tệp mã nguồn/tiêu đề trong cùng thư mục rồi chạy:

g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp

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 dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

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

N M
C_1 C_2 ... C_{N*M}

Trong đó \(C_i\) là màu của chiếc bánh \(i\), thuộc đoạn \([1,N]\). Đây là thông tin riêng của trình chấm, không phải tham số truyền cho Solve.

Nếu chương trình được chấp nhận, trình chấm mẫu xuất số lần gọi Query, chẳng hạn Accepted: 2022. Nếu chương trình bị chấm sai, trình chấm mẫu xuất loại lỗi, chẳng hạn Wrong Answer [4]. Nếu đồng thời vi phạm nhiều điều kiện, trình chấm mẫu chỉ báo một loại lỗi.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của những hàm được mô tả ở trên, không đọc đầu vào chuẩn.

Dữ liệu ra

Bài nộp không ghi đầu ra chuẩn. Kết quả được gửi qua các hàm gọi lại được mô tả ở trên.

Ràng buộc

• \(1\le C_i\le N\) với mọi \(1\le i\le N\times M\).
• Với mỗi màu \(j\) (\(1\le j\le N\)), có đúng \(M\) chỉ số \(i\) thỏa mãn \(C_i=j\).
• \(N\), \(M\) và mọi \(C_i\) đều là số nguyên.

Phân nhóm

1. \(2\) điểm: \(N=4\), \(M=4\).
2. \(5\) điểm: \(N=100\), \(M=10\).
3. \(15\) điểm: \(N=200\), \(M=25\).
4. \(78\) điểm: \(N=400\), \(M=25\).

Ví dụ giao tiếp

Ví dụ 1

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

3 2
3 3 1 2 1 2

Lời gọi và giá trị trả về

Solve(3, 2)
Query([]) -> 0
Query([4, 2, 1, 3]) -> 1
Query([3, 4, 5]) -> 0
Query([2, 6, 5]) -> 1
Query([6, 5, 4, 3, 2, 1]) -> 2
Answer([1, 6, 5])
Answer([2, 3, 4])

Giải thích

Đầu vào này không thỏa mãn ràng buộc của bất kỳ nhóm nào. Tệp sample-02.txt trong gói hỗ trợ thỏa mãn ràng buộc của nhóm \(1\).

Nguồn

Nguồn: JOI 2021/2022, Spring Training Camp, Contest 4. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.