← 返回题目列表

Codeforces · 1936/A

A. 位运算向导

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

这是一个交互问题。

有一个秘密序列$$$p_0, p_1, \ldots, p_{n-1}$$$,它是$$$\{0,1,\ldots,n-1\}$$$的排列。

您需要找到任意两个索引 $$$i$$$ 和 $$$j$$$ 使得 $$$p_i \oplus p_j$$$ 最大化,其中 $$$\oplus$$$ 表示按位异或运算。

为此,您可以提出疑问。每个查询都具有以下形式:您可以选择任意索引 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ ($$$0 \le a,b,c,d < n$$$)。接下来,陪审团计算 $$$x = (p_a \mid p_b)$$$ 和 $$$y = (p_c \mid p_d)$$$,其中 $$$|$$$ 表示按位或运算。最后,您会收到 $$$x$$$ 和 $$$y$$$ 之间的比较结果。换句话说,系统会告诉您是否 $$$x < y$$$、$$$x > y$$$ 或 $$$x = y$$$。

请找到任意两个索引 $$$i$$$ 和 $$$j$$$ ($$$0 \le i,j < n$$$),使得 $$$p_i \oplus p_j$$$ 是所有此类对中的最大值,最多使用 $$$3n$$$ 查询。如果有多对满足条件的索引,则可以输出其中任意一对。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

互动

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^4$$$)。此时,选择排列$$$p_0, p_1, \ldots, p_{n-1}$$$。此任务中的交互器不具有适应性。换句话说,序列 $$$p$$$ 在每个测试用例中都是固定的,并且在交互过程中不会改变。

要提出查询,您需要选择四个索引 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ ($$$0 \le a,b,c,d < n$$$) 并打印以下形式的行:

- “?a b c d”

之后,您会收到:

- "<" 如果 $$$(p_a \mid p_b) < (p_c \mid p_d)$$$;
- "= if $$$(p_a \mid p_b) = (p_c \mid p_d)$$$;
- ">" 如果 $$$(p_a \mid p_b) > (p_c \mid p_d)$$$。

您最多可以进行 $$$3n$$$ 这种形式的查询。

接下来,如果您的程序找到一对索引 $$$i$$$ 和 $$$j$$$ ($$$0 \le i, j < n$$$) 使得 $$$p_i \oplus p_j$$$ 最大化,则打印以下形式的行:

- “!i j”

请注意,此行不被视为查询,并且在计算所请求的查询数时不会被考虑在内。

此后,继续下一个测试用例。

如果您在交互过程中进行超过 $$$3n$$$ 查询,您的程序必须立即终止,并且您将收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印测试用例的查询或答案后,不要忘记输出行尾并刷新输出。否则,您将得到 Idleness Limit Exceeded 的判决。为此,请使用:

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。

黑客

要破解,请遵循以下测试格式。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^4$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_0,p_1,\ldots,p_{n-1}$$$,表示从 $$$0$$$ 到 $$$n - 1$$$ 的整数排列。

所有测试用例的 $$$n$$$ 总和不应超过 $$$10^4$$$。

示例

输入 #1

2
4

<

=

>

2

输出 #1

? 0 2 3 1

? 1 1 2 3

? 1 2 0 3

! 3 2

! 0 1

注意

在第一个测试用例中,隐藏排列是 $$$p=[0,3,1,2]$$$。

对于查询“? 0 2 3 1”,陪审团返回“<”,因为 $$$(p_0 \mid p_2) = (0 \mid 1) =1 < (p_3 \mid p_1) = (2 \mid 3) = 3$$$。

对于查询“? 1 1 2 3”,陪审团返回“=”,因为 $$$(p_1 \mid p_1) = (3\mid 3)= 3 = (p_2 \mid p_3) = (1 \mid 2)=3$$$。

对于查询“? 1 2 0 3”,陪审团返回“">”,因为 $$$(p_1 \mid p_2) = (3 \mid 1) = 3 > (p_0 \mid p_3) = (0\mid 2)=2$$$。

答案 $$$i = 3$$$ 和 $$$j = 2$$$ 是有效的: $$$(p_3 \o​​plus p_2) = (2 \oplus 1) = 3$$$ 确实等于 $$$p_i \oplus p_j$$$ 的最大可能值。另一个有效答案是 $$$i=0$$$ 和 $$$j=1$$$。由于查询次数不超过$$$3n=12$$$,因此认为答案是正确的。

在第二个测试用例中,$$$n = 2$$$,因此 $$$p$$$ 是 $$$[0, 1]$$$ 或 $$$[1, 0]$$$。无论如何,$$$p_0 \oplus p_1 = 1$$$ 是最大可能的。