← 返回题目列表

Codeforces · 1451/E1

E1. 按位查询(简单版)

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

简单版本和困难版本之间的唯一区别是查询数量的限制。

这是一个交互问题。

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]$$$。