← 返回题目列表

Codeforces · 1147/E

E. 彩虹币

中文机器翻译题面 查看原题

Carl 有 $$$n$$$ 各种颜色的硬币,他想将它们分类成堆。这些硬币被标记为 $$$1,2,\ldots,n$$$,并且每个硬币恰好是红色、绿色或蓝色之一。他想将硬币分成三堆,其中一堆包含所有红色硬币,一堆包含所有绿色硬币,一堆包含所有蓝色硬币。

不幸的是,卡尔是色盲,所以这个任务对他来说是不可能的。幸运的是,他有一个朋友可以拿一对硬币并告诉卡尔它们的颜色是否相同。卡尔相信他现在可以通过他的朋友对硬币进行分类。堆的顺序并不重要,只要所有相同颜色的硬币都在一堆中,并且没有两个不同颜色的硬币在同一堆中即可。

他的朋友将批量回答有关多对硬币的问题,并将并行回答所有这些对的问题。每批中每枚硬币最多应为一对。同一枚硬币可以出现在不同的批次中。

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$$$ 的位串,其中如果 $$$x_i$$$ 和 $$$y_i$$$ 颜色相同,则第 $$$i$$$ 个字符为“1”,否则为“0”。如果您提出无效的查询,法官将回复 $$$-1$$$。确保立即退出,以避免得到其他判决。

当您准备好回答时,请打印四行。

第一行包含“A $$$k_1\ k_2\ k_3$$$”($$$0 \leq k_1,k_2,k_3$$$ 和 $$$k_1+k_2+k_3 = n$$$)。这些表示三堆的大小。

下一行有 $$$k_1$$$ 整数,即第一堆硬币的标签。

下一行有 $$$k_2$$$ 整数,即第二堆硬币的标签。

下一行有 $$$k_3$$$ 整数,第三堆中的标签硬币。

每枚硬币必须恰好出现在一堆中。

每个测试用例最多只能要求 $$$7$$$ 批次。

打印查询和答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

要破解,请使用以下格式。请注意,您只能使用一个测试用例进行破解。

第一行应包含单个整数 $$$t$$$ ($$$t=1$$$)。

第二行应包含单个字符串 $$$s$$$,仅包含字符“R”、“G”、“B” ($$$1 \leq |s| \leq 10^5$$$)。该字符串中的第 $$$i$$$ 字符代表第 $$$i$$$ 硬币的颜色。

示例

输入 #1

3
3
1
1
1
3
1
0
0
6
000
010
100
001
000

输出 #1

Q 1 1 2
Q 1 2 3
Q 1 1 3
A 3 0 0
1 2 3


Q 1 1 3
Q 1 2 3
Q 1 1 2
A 2 0 1
1 3

2
Q 3 1 2 3 4 5 6
Q 3 1 3 2 5 4 6
Q 3 1 4 2 6 3 5
Q 3 1 5 2 4 3 6
Q 3 1 6 2 3 4 5
A 2 2 2
1 4
2 5
3 6

注意

在示例中,有三个测试用例。

在第一个测试用例中,有三个硬币。我们询问不同批次中的 $$$(1,2)$$$、$$$(2,3)$$$ 和 $$$(1,3)$$$ 对,并得到它们都是相同的颜色。因此,我们知道所有硬币的颜色相同,因此我们可以将它们全部放在一堆。请注意,有些堆可以是空的,并且用空线表示。

在第二个测试用例中,又出现了三个硬币。这次,我们只得到 $$$(1,3)$$$ 相同,而 $$$(1,2)$$$ 和 $$$(2,3)$$$ 不同。因此,一种可能的情况是硬币 $$$1$$$ 和 $$$3$$$ 是红色的,而硬币 $$$2$$$ 是绿色的。

在最后一种情况下,有 $$$6$$$ 硬币。该案例展示了如何在一批中询问和接收多对的答案。