这是一个交互问题。 此外,针对此问题禁用了黑客攻击。
有两个隐藏整数 $$$b$$$ 和 $$$v$$$ 使得 $$$b \in \{0,1\}$$$ 和 $$$0 \le v \lt 2^{30}.$$$ 还有一个隐藏运算 $$$\mathrm{ty},$$$ 可以是 $$$\&$$$ 或 $$$|.$$$ 这里, $$$\&$$$ 表示按位与运算。另外,$$$|$$$表示按位或运算。
你的目标是猜测 $$$b.$$$
交互过程如下:
- 首先,将值 $$$x$$$ 发送到交互器,使得 $$$0 \le x \lt 2^{30}$$$。
- 交互器发回 $$$v\,\mathrm{ty}\,x$$$。正式地,它将发回 $$$o(v,x)$$$,其中 $$o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases}$$
- 然后发送两个数字 $$$m_0$$$ 和 $$$m_1$$$,其中 $$$0 \le m_0, m_1 \lt 2^{30}.$$$
- 最后,交互器将发送回$$$m_b \oplus v,$$$,其中$$$\oplus$$$表示按位异或运算。
交互后,你要输出$$$b$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。请注意,这是给出的唯一初始输入。
互动
首先,您需要输出一个整数 $$$x \, (0 \le x \lt 2^{30})$$$ — 发送给交互器的初始值。
作为响应,您将收到一个整数 $$$o\,(0 \le o \lt 2^{30})$$$ — $$$v\,\mathrm{ty}\,x.$$$ 运算的结果 $$$o(v,x)$$$
接下来,您将发送一行包含两个整数 $$$m_0, m_1\,(0 \le m_0, m_1 \lt 2^{30}).$$$
最后,接收一个整数 $$$r\,(0 \le r \lt 2^{30})$$$ — $$$m_b \oplus v.$$$ 的值
请注意,交互器是 部分自适应 — 特别是, $$$v$$$ 的选择可以由初始输入 $$$x$$$ 决定,但是 所有隐藏值将在之后修复.
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
3 0 315 3 35 5 5
输出复制
2 314 159 0 3 12 34 1 0 0 0 1
注意
示例交互过程如下:
| 解决方案 | 互动者 | 说明 |
| $$$3$$$ | 有 $$$3$$$ 测试用例。 | |
| $$$2$$$ | 解决方案选择 $$$x = 2$$$。 | |
| $$$0$$$ | 交互器发回 $$$x\,\mathrm{ty}\,v = 2\,\&\,1 = 0.$$$ | |
| $$$314$$$ $$$159$$$ | 解决方案发送 $$$m_0 = 314$$$ 和 $$$m_1 = 159.$$$ | |
| $$$315$$$ | 交互者响应 $$$m_b \oplus v = m_0 \oplus v = 315.$$$ | |
| $$$0$$$ | 解确定 $$$b = 0.$$$ | |
| $$$3$$$ | 下一个测试用例开始。解决方案选择 $$$x = 3$$$。 | |
| $$$3$$$ | 交互器发回 $$$x\,\mathrm{ty}\,v = 3\,|\,1 = 3.$$$ | |
| $$$12$$$ $$$34$$$ | 解决方案发送 $$$m_0 = 12$$$ 和 $$$m_1 = 34.$$$ | |
| $$$35$$$ | 交互者响应 $$$m_b \oplus v = m_1 \oplus v = 35.$$$ | |
| $$$1$$$ | 解确定 $$$b = 1.$$$ | |
| $$$0$$$ | 最终测试用例开始。解决方案选择 $$$x = 0$$$。 | |
| $$$5$$$ | 交互器发回 $$$x\,\mathrm{ty}\,v = 0\,|\,5 = 5.$$$ | |
| $$$0$$$ $$$0$$$ | 解决方案发送 $$$m_0 = 0$$$ 和 $$$m_1 = 0.$$$ | |
| $$$5$$$ | 交互者响应 $$$m_b \oplus v = m_1 \oplus v = 5.$$$ | |
| $$$1$$$ | 解确定 $$$b = 1.$$$ |
请注意,示例解决方案进行的查询可能无法产生足够的信息来确定隐藏位 $$$b.$$$ 此外,示例交互中的空行是为了可读性而给出的,不需要在解决方案中输出。
测试用例中的隐藏值如下所示。
| 测试# | $$$v$$$ | $$$b$$$ | $$$\mathrm{ty}$$$ |
| $$$1$$$ | $$$1$$$ | $$$0$$$ | $$$\&$$$ |
| $$$2$$$ | $$$1$$$ | $$$1$$$ | $$$|$$$ |
| $$$3$$$ | $$$5$$$ | $$$1$$$ | $$$|$$$ |