P9529 [JOISC 2022] 一流团子师傅

JOISC2022 D4T1 **特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `dango3.h`，而需要把 `dango3.h` 中的内容加入文件的开头。即，在程序中 `void Solve(int N, int M)` 的前面加入以下几行语句：** ```cpp #include void Solve(int N, int M); int Query(const std::vector &x); void Answer(const std::vector &a); ```

JOI 君是一位专业的团子师傅。在 JOI 君的店里，团子的颜色很有讲究。一共有 $N$ 种颜色，编号为 $1,2,\dots,N$。 **一流团子串**是 JOI 君的店里的招牌食品。制作一个一流团子串，需要将 $N$ 个**颜色不同**的团子串在一根竹签上。 对于每一种颜色，JOI 君都制作了 $M$ 个这种颜色的团子。因此，JOI 君总共有了 $NM$ 个团子。这些团子被编号为 $1,2,\dots,NM$。使用这些团子和 $M$ 根竹签，JOI 君希望串出 $M$ 个一流团子串。 为了避免在颜色上犯错误，JOI 君将会启用他的团子检测器。如果 JOI 君输入一些团子的编号，团子检测器会返回使用这些团子能制作的一流团子串的个数的最大值。当然，前提是充分使用竹签。 JOI 君希望能通过使用若干次团子检测器将 $NM$ 个团子分为 $M$ 组。其中，每一组包含 $N$ 个团子，且每种颜色的团子恰有一个。 JOI 君想在使用不超过 $50\,000$ 次团子检测器的前提下完成这件事。 请写一个程序，对于给定的团子的信息，实现 JOI 君使用不超过 $50\,000$ 次团子检测器来完成任务的策略。 --- **【实现细节】** 你的程序需要实现以下函数。 - `void Solve(int N, int M)`。 对于每组测试数据，该函数会被调用恰好一次。 - 参数 $\texttt N$ 是团子的颜色数 $N$。 - 参数 $\texttt M$ 是 JOI 君想制作的一流团子串的个数 $M$。 你的程序可以调用以下函数。 - `int Query(const std::vector &x)`。 你的程序可以通过调用这个函数来使用团子检测器。 - 参数 `x` 是输入给团子检测器的团子的编号列表。 - 该函数返回使用 `x` 中的团子能制作的一流团子串的最大值。 - `x` 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 **Wrong Answer [1]**。 - `x` 中的元素应当互不相同。否则你的程序会被判定为 **Wrong Answer [2]**。 - 你的程序不得调用该函数超过 $50\,000$ 次。否则你的程序会被判定为 **Wrong Answer [3]**。 - `void Answer(const std::vector &a)`。 你的程序可以通过调用这个程序来报告分组方案。 - 参数 `a` 是你分出的一组团子的编号列表。 - `a` 的长度应当为 $N$。否则你的程序会被判定为 **Wrong Answer [4]**。 - `a` 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 **Wrong Answer [5]**。 - 在整个过程中，同一个团子不能出现在参数中多于一次。否则你的程序会被判定为 **Wrong Answer [6]**。 - 如果用 `a` 中的团子并不能制作一个一流团子串，你的程序会被判定为 **Wrong Answer [7]**。 - 该函数应当被调用恰好 $M$ 次。否则你的程序会被判定为 **Wrong Answer [8]**。 **【提示】** - 你的程序可以实现其他函数以供内部使用，或者使用全局变量。 - 你的程序不得使用标准输入输出流，也不得以任何方式访问任何文件。然而，你可以输出调试信息到标准错误流。 **【编译与测试运行】** 你可以从「附加文件」中下载样例评分器来测试你的程序。「附加文件」中也提供了你应当提交的程序的一个样例。 样例评分器即 `grader.cpp`。为了测试你的程序，请将 `grader.cpp,dango3.cpp` 放置在同一个目录下，并执行如下命令来编译你的程序。 `g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp` 若编译成功，将会生成一个可执行文件 `grader`。 请注意，实际使用的评分器与下发的样例评分器不同。样例评分器仅会有单个进程，从标准输入中读取输入数据并将结果输出到标准输出。 **【样例评分器输入格式】** 第一行，两个正整数 $N,M$。表示团子的颜色数和 JOI 君想制作的一流团子串的个数。 第二行，$N\times M$ 个正整数 $C_1,C_2,\dots,C_{NM}$。其中 $C_i$ 是一个 $[1,N]$ 内的正整数，表示第 $i$ 个团子的颜色。 **【样例评分器输出格式】** - 如果你的程序被判定为正确，样例评分器会输出调用 `Query` 的次数，如 “$\texttt{Accepted: 2022}$”。 - 如果你的程序被判定为任意一种 Wrong Answer，样例评分器会输出其类型，如 “$\texttt{Wrong Answer [4]}$”。 如果你的程序属于多种 Wrong Answer，样例评分器只会输出其中一种。

无

无

**【样例交互】** 这里是样例评分器的一组样例输入和对应的交互过程。 ```plain 3 2 3 3 1 2 1 2 ``` |调用|调用|返回值| |:-|:-|:-| |$\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])}$|| 注意，这组样例**不满足任意子任务的限制**。 从「附加文件」中可以下载到 $\texttt{sample-02.txt}$，其满足子任务 $1$ 的限制。 **【数据范围】** 对于所有测试数据，满足： - $1 \le C_i \le N$ $(1 \le i \le NM)$。 - 对于每个 $j$ $(1 \le j \le N)$，恰有 $M$ 个 $i$ $(1 \le i \le NM)$ 满足 $C_i = j$。 - $N,M$ 是正整数。 - $C_i$ $(1 \le i \le NM)$ 是一个 $[1,N]$ 内的整数。 详细子任务附加限制及分值如下表所示： |子任务编号|附加限制|分值| |:-:|:-:|:-:| |$1$|$N=M=4$|$2$| |$2$|$N=100$，$M=10$|$5$| |$3$|$N=200$，$M=25$|$15$| |$4$|$N=400$，$M=25$|$78$|