CF1936A Bitwise Operation Wizard

这是一个交互题。 有一个秘密序列 $p_0, p_1, \ldots, p_{n-1}$，它是 $\{0,1,\ldots,n-1\}$ 的一个排列。 你需要找到任意一对下标 $i$ 和 $j$，使得 $p_i \oplus p_j$ 的值最大，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 为此，你可以进行若干次查询。每次查询的形式如下：你任选四个下标 $a$、$b$、$c$、$d$（$0 \le a,b,c,d < n$）。接着，评测器会计算 $x = (p_a \mid p_b)$ 和 $y = (p_c \mid p_d)$，其中 $|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。最后，你会收到 $x$ 和 $y$ 的比较结果。也就是说，你会被告知 $x < y$、$x > y$ 或 $x = y$。 请在最多 $3n$ 次查询内，找到一对下标 $i$ 和 $j$（$0 \le i,j < n$），使得 $p_i \oplus p_j$ 在所有可能的下标对中取到最大值。如果有多组满足条件的下标对，你可以输出任意一组。

每个测试点包含多组测试数据。第一行包含测试组数 $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)$，则返回 ""。 你最多可以进行 $3n$ 次此类查询。 接下来，如果你的程序找到了满足 $p_i \oplus p_j$ 最大的下标对 $i$ 和 $j$（$0 \le i, j < n$），请输出如下格式的一行： - "! i j" 注意，这一行不计入查询次数。 之后，进入下一组测试数据。 如果你在一次交互中进行了超过 $3n$ 次查询，你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，你的程序会继续从已关闭的流中读取数据，可能会得到任意判定。 每次输出查询或答案后，不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness Limit Exceeded 判定。具体操作如下： - C++ 使用 fflush(stdout) 或 cout.flush()； - Java 使用 System.out.flush()； - Pascal 使用 flush(output)； - Python 使用 stdout.flush()； - 其它语言请参考相关文档。 保证所有测试数据中 $n$ 的总和不超过 $10^4$。 Hack 如需 Hack，请按照以下格式编写测试数据。 第一行包含测试组数 $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$。

在第一个测试点中，隐藏的排列为 $p=[0,3,1,2]$。 对于查询 "? 0 2 3 1"，评测器返回 ""，因为 $(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$ 都是最大可能值。 由 ChatGPT 4.1 翻译