简单版本和困难版本之间的唯一区别是查询数量的限制。
这是一个交互问题。
Ridbit 有一个包含 $$$n$$$ 整数的隐藏数组 $$$a$$$,他希望 Ashish 猜出该数组。请注意 $$$n$$$ 是 2 的幂。 Ashish 可以提出三种不同类型的问题。它们的形式是
- AND $$$i$$$ $$$j$$$:要求元素 $$$a_i$$$ 和 $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$ 的按位与
- OR $$$i$$$ $$$j$$$:要求元素 $$$a_i$$$ 和 $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$ 按位或
- XOR $$$i$$$ $$$j$$$:要求元素 $$$a_i$$$ 和 $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$ 按位异或
你能帮助 Ashish 猜出数组的元素吗?
在此版本中,每个元素采用 $$$[0, n-1]$$$(含)范围内的值,并且 Ashish 最多可以提出 $$$n+2$$$ 查询。
输入
输入的第一行包含一个整数 $$$n$$$ $$$(4 \le n \le 2^{16})$$$ - 数组的长度。保证 $$$n$$$ 是 2 的幂。
互动
要询问查询,请打印包含以下内容之一的单行(不带引号)
- “AND i j”
- “或 i j”
- “异或 i j”
对于每个查询,您将收到一个整数 $$$x$$$,其值取决于查询的类型。如果查询的索引无效或者超出查询数量,您将得到 $$$x = -1$$$。在这种情况下,您应该立即终止该程序。
当您猜出数组的元素后,打印一行“!”(不带引号),后跟 $$$n$$$ 空格分隔的整数 - 数组的元素。
猜测数组不计入所请求的查询数。
交互器不具有自适应性。数组 $$$a$$$ 不会随查询而改变。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解该解决方案,请使用以下测试格式:
在第一行打印一个整数 $$$n$$$ $$$(4 \le n \le 2^{16})$$$ - 数组的长度。它必须是 2 的幂。下一行应包含 $$$n$$$ 范围内以空格分隔的整数 $$$[0, n-1]$$$ — 数组 $$$a$$$。
示例
输入 #1
4 0 2 3
输出 #1
OR 1 2 OR 2 3 XOR 2 4 ! 0 0 2 3
注意
示例中的数组 $$$a$$$ 为 $$$[0, 0, 2, 3]$$$。