CF1451E2 Bitwise Queries (Hard Version)

本题的简单版和困难版的唯一区别在于查询次数的限制。 这是一个交互题。 Ridbit 有一个长度为 $n$ 的隐藏整数数组 $a$，他希望 Ashish 猜出这个数组。注意，$n$ 是 $2$ 的幂。Ashish 可以进行三种不同类型的查询，形式如下： - AND $i$ $j$：询问 $a_i$ 和 $a_j$ 的按位与（bitwise AND）结果（$1 \leq i, j \leq n$，$i \neq j$）。 - OR $i$ $j$：询问 $a_i$ 和 $a_j$ 的按位或（bitwise OR）结果（$1 \leq i, j \leq n$，$i \neq j$）。 - XOR $i$ $j$：询问 $a_i$ 和 $a_j$ 的按位异或（bitwise XOR）结果（$1 \leq i, j \leq n$，$i \neq j$）。 你能帮助 Ashish 猜出数组的所有元素吗？ 在本题版本中，每个元素的取值范围为 $[0, n-1]$（包含 $0$ 和 $n-1$），且 Ashish 最多只能询问 $n+1$ 次。

输入的第一行包含一个整数 $n$（$4 \leq n \leq 2^{16}$）——数组的长度。保证 $n$ 是 $2$ 的幂。

每次查询时，输出一行，内容为以下三种之一（不含引号）： - "AND i j" - "OR i j" - "XOR i j" 其中 $i$ 和 $j$ 满足 $1 \leq i, j \leq n$，且 $i \neq j$，表示要查询的下标。对于每次查询，你将收到一个整数 $x$，其值取决于查询类型。如果查询的下标无效或查询次数超过限制，你将收到 $x = -1$，此时应立即终止程序。 当你猜出整个数组后，输出一行，格式为 "! "（不含引号），后跟 $n$ 个用空格分隔的整数，表示数组 $a$ 的所有元素。 猜测数组的操作不计入查询次数。 交互器不会自适应。数组 $a$ 在查询过程中不会发生变化。 每次输出查询后，不要忘记输出换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而失败。具体做法如下： - C++：使用 fflush(stdout) 或 cout.flush() - Java：使用 System.out.flush() - Pascal：使用 flush(output) - Python：使用 stdout.flush() - 其他语言请参考相关文档。 Hack 格式 要 Hack 其他解法，请使用如下测试格式： 第一行输出一个整数 $n$（$4 \leq n \leq 2^{16}$），保证 $n$ 是 $2$ 的幂。第二行输出 $n$ 个用空格分隔的整数，范围为 $[0, n-1]$，表示数组 $a$。

示例中的数组 $a$ 为 $[0, 0, 2, 3]$。 由 ChatGPT 4.1 翻译