这是一个交互问题。
有一个秘密序列$$$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 \oplus 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$$$ 是最大可能的。