UOJ Logo Universal Online Judge

UOJ

#731. 【JOISC2022】制作团子 3

附件下载 统计

这是一道交互题。

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$ 次团子检测器来完成任务的策略。

任务

本题只支持符合 C++11 及以上标准的 C++ 语言。

你必须引用 dango3.h

你需要实现如下过程:

void Solve(int N, int M);

对于每组测试数据,该函数会被调用恰好一次。

  • 参数 $\texttt N$ 是团子的颜色数 $N$。
  • 参数 $\texttt M$ 是 JOI 君想制作的一流团子串的个数 $M$。

你的程序可以调用以下函数。

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

你的程序可以通过调用这个函数来使用团子检测器。

  • 参数 $\texttt x$ 是输入给团子检测器的团子的编号列表。
  • 该函数返回使用 $\texttt x$ 中的团子能制作的一流团子串的最大值。
  • $\texttt x$ 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 Wrong Answer [1]
  • $\texttt x$ 中的元素应当互不相同。否则你的程序会被判定为 Wrong Answer [2]
  • 你的程序不得调用该函数超过 $50\,000$ 次。否则你的程序会被判定为 Wrong Answer [3]
void Answer(const std::vector<int> &a);

你的程序可以通过调用这个程序来报告分组方案。

  • 参数 $\texttt a$ 是你分出的一组团子的编号列表。
  • $\texttt a$ 的长度应当为 $N$。否则你的程序会被判定为 Wrong Answer [4]
  • $\texttt a$ 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 Wrong Answer [5]
  • 在整个过程中,同一个团子不能出现在参数中多于一次。否则你的程序会被判定为 Wrong Answer [6]
  • 如果用 $\texttt a$ 中的团子并不能制作一个一流团子串,你的程序会被判定为 Wrong Answer [7]
  • 该函数应当被调用恰好 $M$ 次。否则你的程序会被判定为 Wrong Answer [6]

提示

  • 你的程序可以实现其他函数以供内部使用,或者使用全局变量。
  • 你的程序不得使用标准输入输出流,也不得以任何方式访问任何文件。然而,你可以输出调试信息到标准错误流。

样例评分器

见附件下载中的 grader.cpp

样例输入格式

第一行,两个正整数 $N,M$。表示团子的颜色数和 JOI 君想制作的一流团子串的个数。

第二行,$N\times M$ 个正整数 $C_1,C_2,\dots,C_{NM}$。其中 $C_i$ 是一个 $[1,N]$ 内的正整数,表示第 $i$ 个团子的颜色。

样例输出格式

  • 如果你的程序被判定为正确,样例评分器会输出调用 $\texttt{Query}$ 的次数,如 Accepted: 2022
  • 如果你的程序被判定为任意一种 Wrong Answer,样例评分器会输出其类型,如 Wrong Answer [4]

如果你的程序属于多种 Wrong Answer,样例评分器只会输出其中一种。

样例一

input

3 2
3 3 1 2 1 2

explanation

以下是一组合法的交互过程:

调用 调用 返回值
$\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])}$ $~$

注意,这组样例不满足任意子任务的限制

样例二

见附件下载中的 ex_dango3.in

这组样例满足子任务 $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$

时间限制:$\texttt{10s}$

空间限制:$\texttt{1GB}$