← 返回题目列表

Codeforces · 1867/C

C. Salyg1n 和 MEX 游戏

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

这是一个交互问题!

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