Background

JOISC2022 D4T1.

Special reminder: due to the special nature of Luogu’s interactive mechanism, you cannot include dango3.h in your program. Instead, you need to paste the content of dango3.h at the beginning of your file. That is, add the following lines before void Solve(int N, int M) in your program:

#include <vector>

void Solve(int N, int M);

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

Problem Description

JOI is a professional dango maker. In JOI’s shop, the colors of dango are handled very carefully. There are a total of $N$ colors, numbered $1,2,\dots,N$.

A first-class dango skewer is the signature product of JOI’s shop. To make one first-class dango skewer, you need to put $N$ dango of different colors onto one bamboo stick.

For each color, JOI has made $M$ dango of that color. Therefore, JOI has a total of $NM$ dango. These dango are numbered $1,2,\dots,NM$. Using these dango and $M$ bamboo sticks, JOI wants to make $M$ first-class dango skewers.

To avoid making mistakes about colors, JOI will use his dango detector. If JOI inputs the indices of some dango, the detector will return the maximum possible number of first-class dango skewers that can be made using those dango. Of course, this is under the condition that the bamboo sticks are fully used.

JOI wants to use the dango detector several times to divide the $NM$ dango into $M$ groups, where each group contains $N$ dango and contains exactly one dango of each color.

JOI wants to finish this task using the dango detector no more than $50\,000$ times.

Please write a program that, given the information about the dango, implements a strategy for JOI to complete the task using the dango detector no more than $50\,000$ times.

Implementation Details

Your program must implement the following function.

• void Solve(int N, int M).
  For each test case, this function is called exactly once.
  • Parameter N is the number of dango colors $N$.
  • Parameter M is the number of first-class dango skewers JOI wants to make, $M$.

Your program may call the following functions.

• int Query(const std::vector<int> &x).
  Your program can call this function to use the dango detector.

  • Parameter x is the list of indices of dango given to the detector.
  • The function returns the maximum number of first-class dango skewers that can be made using the dango in x.
  • Each element of x must be an integer in $[1,NM]$. Otherwise, your program will be judged Wrong Answer [1].
  • The elements of x must be pairwise distinct. Otherwise, your program will be judged Wrong Answer [2].
  • Your program must not call this function more than $50\,000$ times. Otherwise, your program will be judged Wrong Answer [3].

• void Answer(const std::vector<int> &a).
  Your program can call this function to report a grouping scheme.

  • Parameter a is the list of indices of one group of dango you formed.
  • The length of a must be $N$. Otherwise, your program will be judged Wrong Answer [4].
  • Each element of a must be an integer in $[1,NM]$. Otherwise, your program will be judged Wrong Answer [5].
  • Throughout the whole process, the same dango must not appear in the parameter more than once. Otherwise, your program will be judged Wrong Answer [6].
  • If the dango in a cannot form a first-class dango skewer, your program will be judged Wrong Answer [7].
  • This function must be called exactly $M$ times. Otherwise, your program will be judged Wrong Answer [8].

Hints

• Your program may implement other functions for internal use, or use global variables.
• Your program must not use standard input/output streams, and must not access any files in any way. However, you may print debug information to the standard error stream.

Compilation and Test Run

You can download the sample grader from “Additional Files” to test your program. “Additional Files” also provides a sample of the program you should submit.

The sample grader is grader.cpp. To test your program, put grader.cpp,dango3.cpp in the same directory, and compile your program using the following command.

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

If compilation succeeds, an executable file grader will be generated.

Note that the actual grader used is different from the provided sample grader. The sample grader only has a single process: it reads input from standard input and outputs the result to standard output.

Sample Grader Input Format

The first line contains two positive integers $N,M$, which represent the number of colors and the number of first-class dango skewers JOI wants to make.

The second line contains $N\times M$ positive integers $C_1,C_2,\dots,C_{NM}$. Here, $C_i$ is a positive integer in $[1,N]$, representing the color of the $i$-th dango.

Sample Grader Output Format

• If your program is judged correct, the sample grader outputs the number of calls to Query, such as “$\texttt{Accepted: 2022}$”.
• If your program is judged as any kind of Wrong Answer, the sample grader outputs its type, such as “$\texttt{Wrong Answer [4]}$”.

If your program falls into multiple Wrong Answer types, the sample grader will output only one of them.

Hint

Sample Interaction

Here is a sample input for the sample grader and the corresponding interaction process.

3 2
3 3 1 2 1 2

Note that this sample does not satisfy the limits of any subtask.

You can download $\texttt{sample-02.txt}$ from “Additional Files”. It satisfies the limits of Subtask $1$.

Constraints

For all testdata, the following hold:

• $1 \le C_i \le N$ $(1 \le i \le NM)$.
• For each $j$ $(1 \le j \le N)$, there are exactly $M$ indices $i$ $(1 \le i \le NM)$ such that $C_i = j$.
• $N,M$ are positive integers.
• $C_i$ $(1 \le i \le NM)$ is an integer in $[1,N]$.

The additional constraints and scores of the subtasks are given in the table below:

Translated by ChatGPT 5