P9529 [JOIST 2022] First-Class Dango Maker / Super Dango Maker

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:** ```cpp #include void Solve(int N, int M); int Query(const std::vector &x); void Answer(const std::vector &a); ```

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 &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 &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.

N/A

N/A

**Sample Interaction** Here is a sample input for the sample grader and the corresponding interaction process. ```plain 3 2 3 3 1 2 1 2 ``` |Call|Call|Return value| |:-|:-|:-| |$\texttt{Solve(3, 2)}$||| ||$\texttt{Query([])}$|$\texttt 0$| ||$\texttt{Query([4, 2, 1, 3])}$|$\texttt 1$| ||$\texttt{Query([3, 4, 5])}$|$\texttt 0$| ||$\texttt{Query([2, 6, 5])}$|$\texttt 1$| ||$\texttt{Query([6, 5, 4, 3, 2, 1])}$|$\texttt 2$| ||$\texttt{Answer([1, 6, 5])}$|| ||$\texttt{Answer([2, 3, 4])}$|| 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: |Subtask ID|Additional constraints|Score| |:-:|:-:|:-:| |$1$|$N=M=4$|$2$| |$2$|$N=100$, $M=10$|$5$| |$3$|$N=200$, $M=25$|$15$| |$4$|$N=400$, $M=25$|$78$| Translated by ChatGPT 5