这是一个交互问题!
salyg1n 给了 Alice 一组 $$$S$$$ 的 $$$n$$$ 不同整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq 10^9$$$)。爱丽丝决定用这组游戏与鲍勃玩一场游戏。游戏规则如下:
- 玩家轮流进行,爱丽丝先行。
- Alice 一步将一个数字 $$$x$$$ ($$$0 \leq x \leq 10^9$$$) 添加到集合 $$$S$$$ 中。移动时集合 $$$S$$$ 不得包含数字 $$$x$$$。
- 鲍勃一步从 $$$S$$$ 集合中删除了一个数字 $$$y$$$。集合 $$$S$$$ 必须包含移动时的数字 $$$y$$$。此外,数字 $$$y$$$ 必须严格小于 Alice 添加的最后一个数字。
- 当鲍勃无法移动或 $$$2 \cdot n + 1$$$ 移动后游戏结束(在这种情况下,爱丽丝的移动将是最后一个)。
- 游戏结果为$$$\operatorname{MEX}\dagger(S)$$$(游戏结束时为$$$S$$$)。
- Alice 的目标是最大化结果,而 Bob 的目标是最小化结果。
令 $$$R$$$ 为两名玩家都发挥最佳状态时的结果。在这个问题中,您扮演爱丽丝,对抗扮演鲍勃的陪审团程序。你的任务是为 Alice 实施一个策略,使得游戏的结果始终至少为 $$$R$$$。
$$$\dagger$$$ $$$\operatorname{MEX}$$$ 一组整数 $$$c_1, c_2, \ldots, c_k$$$ 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。例如,$$$\operatorname{MEX}(\{0, 1, 2, 4\})$$$ $$$=$$$ $$$3$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) - 测试用例的数量。
互动
你的程序和陪审团程序之间的交互首先读取一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) - 游戏开始前集合 $$$S$$$ 的大小。
然后,读取一行 - $$$n$$$ 不同的整数 $$$s_i$$$ $$$(0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9)$$$ - 给 Alice 的集合 $$$S$$$。
要进行移动,请输出一个整数 $$$x$$$ ($$$0 \leq x \leq 10^9$$$) - 要添加到集合 $$$S$$$ 中的数字。 $$$S$$$ 在移动时不得包含 $$$x$$$。然后,读取一个整数 $$$y$$$ $$$(-2 \leq y \leq 10^9)$$$。
- 如果 $$$0 \leq y \leq 10^9$$$ - Bob 从集合 $$$S$$$ 中删除数字 $$$y$$$。轮到你了!
- 如果$$$y$$$ $$$=$$$ $$$-1$$$ - 游戏结束。之后,继续处理下一个测试用例,如果是最后一个测试用例,则终止程序。
- 否则,$$$y$$$ $$$=$$$ $$$-2$$$。这意味着您进行了无效的查询。您的程序应立即终止以接收“错误答案”的判决。否则,它可能会收到任何其他判决。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
不要尝试解决此问题。
示例
输入 #1
3 5 1 2 3 5 7 7 5 -1 3 0 1 2 0 -1 3 5 7 57 -1
输出 #1
8 57 0 3 0 0
注意
在第一个测试用例中,集合 $$$S$$$ 更改如下:
{$$$1, 2, 3, 5, 7$$$} $$$\到$$$ {$$$1, 2, 3, 5, 7, 8$$$} $$$\到$$$ {$$$1, 2, 3, 5, 8$$$} $$$\到$$$ {$$$1, 2, 3, 5, 8, 57$$$} $$$\到$$$ {$$$1, 2, 3, 8, 57$$$} $$$\到$$$ {$$$0, 1, 2, 3, 8, 57$$$}。游戏结束时,$$$\operatorname{MEX}(S) = 4$$$,$$$R = 4$$$。
在第二个测试用例中,集合 $$$S$$$ 更改如下:
{$$$0, 1, 2$$$} $$$\到$$$ {$$$0, 1, 2, 3$$$} $$$\到$$$ {$$$1, 2, 3$$$} $$$\到$$$ {$$$0, 1, 2, 3$$$}。游戏结束时,$$$\operatorname{MEX}(S) = 4$$$,$$$R = 4$$$。
在第三个测试用例中,集合 $$$S$$$ 更改如下:
{$$$5, 7, 57$$$} $$$\to$$$ {$$$0, 5, 7, 57$$$}。游戏结束时,$$$\operatorname{MEX}(S) = 1$$$,$$$R = 1$$$。