CF1867C Salyg1n and the MEX Game

这是一个交互题！ salyg1n 给了 Alice 一个包含 $n$ 个互不相同整数 $s_1, s_2, \ldots, s_n$ 的集合 $S$（$0 \leq s_i \leq 10^9$）。Alice 决定用这个集合和 Bob 玩一个游戏。游戏规则如下： - 两位玩家轮流操作，Alice 先手。 - 每一轮，Alice 向集合 $S$ 中添加一个整数 $x$（$0 \leq x \leq 10^9$）。此时集合 $S$ 中不能已经包含 $x$。 - 每一轮，Bob 从集合 $S$ 中移除一个整数 $y$。此时集合 $S$ 必须包含 $y$，并且 $y$ 必须严格小于 Alice 上一次添加的数。 - 当 Bob 无法进行操作，或者总共进行了 $2 \cdot n + 1$ 步（此时 Alice 的操作为最后一步）时，游戏结束。 - 游戏的结果为 $\operatorname{MEX}(S)$（即游戏结束时的 $S$）。 - Alice 的目标是最大化结果，Bob 的目标是最小化结果。 设 $R$ 为双方都采取最优策略时的结果。在本题中，你将扮演 Alice，与评测程序扮演的 Bob 对战。你的任务是为 Alice 实现一种策略，使得游戏结果始终不少于 $R$。 $\dagger$ $\operatorname{MEX}$ 表示一组整数 $c_1, c_2, \ldots, c_k$ 的最小非负整数 $x$，使得 $x$ 不在集合 $c$ 中。例如，$\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$，说明你进行了非法操作。你的程序应立即终止，否则可能会收到其它判题结果。 每次输出后不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判题结果。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。不要尝试 hack 本题。

在第一个测试用例中，集合 $S$ 的变化如下： $\{1, 2, 3, 5, 7\} \to \{1, 2, 3, 5, 7, 8\} \to \{1, 2, 3, 5, 8\} \to \{1, 2, 3, 5, 8, 57\} \to \{1, 2, 3, 8, 57\} \to \{0, 1, 2, 3, 8, 57\}$。最终 $\operatorname{MEX}(S) = 4$，$R = 4$。 在第二个测试用例中，集合 $S$ 的变化如下： $\{0, 1, 2\} \to \{0, 1, 2, 3\} \to \{1, 2, 3\} \to \{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$。 由 ChatGPT 4.1 翻译