CF1147E Rainbow Coins

Carl 有 $n$ 枚不同颜色的硬币，他想要将这些硬币分成若干堆。硬币编号为 $1,2,\ldots,n$，每枚硬币的颜色恰好为红色、绿色或蓝色中的一种。他希望将硬币分成三堆，使得一堆包含所有红色硬币，一堆包含所有绿色硬币，一堆包含所有蓝色硬币。 不幸的是，Carl 是色盲，所以他无法完成这个任务。幸运的是，他有一个朋友可以帮忙判断一对硬币是否颜色相同。借助朋友的帮助，Carl 认为他可以完成硬币的分类。堆的顺序无关紧要，只要同色硬币都在同一堆，不同色的硬币不在同一堆即可。 他的朋友会批量回答关于多对硬币的问题，并且会并行地回答所有这些对。每一批中，每枚硬币最多只能出现在一对中。同一枚硬币可以出现在不同的批次中。 Carl 最多只能使用 $7$ 批来完成分类。请你帮助他在分类后找出每一堆的硬币。

你将会得到多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示硬币的数量。如果你读到 $-1$，说明你在上一组数据中输出了无效答案，请立即退出以避免获得其他判定结果。 若要发起一次询问，请输出一行："Q $k\ x_1\ y_1\ \ldots\ x_k\ y_k$"（$1 \leq k \leq n/2, 1 \leq x_i, y_i \leq n, x_i \neq y_i$）。$k$ 表示本批次询问的对数，$x_i, y_i$ 表示第 $i$ 对硬币的编号。每枚硬币在同一批次中最多只能出现一次，所有 $x_i$ 和 $y_i$ 必须互不相同。 裁判会返回一个长度为 $k$ 的二进制字符串，第 $i$ 个字符为 "1" 表示 $x_i$ 和 $y_i$ 颜色相同，为 "0" 表示颜色不同。如果你发起了无效的询问，裁判会返回 $-1$，此时请立即退出以避免获得其他判定结果。 当你准备好输出答案时，请输出四行。 第一行输出 "A $k_1\ k_2\ k_3$"（$0 \leq k_1, k_2, k_3$ 且 $k_1 + k_2 + k_3 = n$），表示三堆的大小。 接下来的三行分别输出每一堆中硬币的编号。每枚硬币必须且只能出现在一堆中。 每个测试用例最多只能询问 $7$ 批。 每次输出询问或答案后，别忘了输出换行并刷新输出缓冲区，否则会因“空闲时间超限”而被判为错误。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档 Hack 格式 如需 Hack，请使用如下格式。注意你只能用一个测试用例进行 Hack。 第一行输入一个整数 $t$（$t=1$）。 第二行输入一个仅包含 "R"、"G"、"B" 的字符串 $s$（$1 \leq |s| \leq 10^5$）。第 $i$ 个字符表示第 $i$ 枚硬币的颜色。

见上文输入格式说明。

例如，有三个测试用例。 在第一个测试用例中，有三枚硬币。我们分别询问 $(1,2)$、$(2,3)$ 和 $(1,3)$，得到它们颜色都相同。因此，我们知道所有硬币颜色相同，可以将它们全部放在一堆。注意有些堆可以为空，用空行表示。 在第二个测试用例中，仍有三枚硬币。这次只有 $(1,3)$ 颜色相同，$(1,2)$ 和 $(2,3)$ 颜色不同。此时，一种可能的情况是硬币 $1$ 和 $3$ 是红色，硬币 $2$ 是绿色。 在最后一个测试用例中，有 $6$ 枚硬币。该用例展示了如何在一批中询问多对硬币并获得答案。 由 ChatGPT 4.1 翻译