P15517 [CEOI 2023] How to Avoid Disqualification in 75 Easy Steps

checker & 翻译来源：loj [#4022. 「CEOI2023」How to Avoid Disqualification in 75 Easy Steps](https://loj.ac/p/4022)。 **提交到洛谷时，您不得包含头文件 `avoid.h`。但请在代码开头添加以下内容：** ```cpp #include void send(std::vector positions); std::vector wait(); ``` **请注意本题特殊的时空限制。**

你正站在那个打开的保险柜前，手里拿着一枚奖牌。但是，当你环顾四周时，你的胜利变成了绝望：你在房间里发现的一条领带上的信息显示，你的助手向科学委员会透露了你的计划！现在，两位委员会主席正躲在大楼里阻止你逃跑。 幸运的是，你在于你的选手朋友交易时剩下了 $R$ 个扫地机器人。你想用这些机器人确定两位主席的位置，以便你逃跑的时候可以避开他们。你可以指示每个机器人在主席可能所在的 $1\ 000$ 个位置中寻找一些。不幸的是，这些机器人的程序十分简单（毕竟你把所有炫酷的都卖给了其他参赛者）。每个机器人只能探测到其侦察位置上是否**至少有一名主席**。 让事情更糟的是，每个机器人在给你带回结果之前，需要一整个小时去探测它所在的位置。因为这会消耗机器人的电，**你只能送出每个机器人一次**。 你不希望晚上的活动迟到，所以你想知道在**最多 $H$ 小时**之后知道主席的位置。特别地，你可能会被迫同时派出多个机器人，而不等前一个机器人返回。你可以假设两位主席一直待在相同的位置上（因为深夜准备比赛题使他们疲惫不堪，动弹不得）。 写一个程序规划侦查任务，并且确定两位主席的位置。 ### 交互 这是一道交互题。你必须实现函数 `pair scout(int R, int H)`，其中 $R$ 和 $H$ 的含义如题目描述。对于每组测试数据，这个函数仅被调用恰好一次，并且应该返回两个整数 $1\le a,b\le 1\ 000$（允许 $a=b$）组成的一个 `pair`，表示两位主席的位置。在 `scout` 函数中，你可以使用交互器提供的其他函数： - `void send(vector P)` 会送出一个机器人侦查位置 `P[0]` 到 `P[k - 1]`（其中 $k$ 表示数组 $P$ 的长度）。位置 `P[i]` 必须是 $1$ 到 $1000$ 之间两两不同的整数。每组测试数据你最多可以调用这个函数 $R$ 次。 - `vector wait()` 表示等一个小时。这个函数会返回一个数组，其中包含一小时前（在上次调用 `wait` 后或程序开始后调用的 `send`）发送的每个机器人的结果。如果第 $i+1$ 个机器人在它侦查的位置探测到了至少有一位主席，则下标 $i$ 的结果为 `1`，否则为 `0`。每组测试数据你最多可以调用这个函数 $H$ 次。 如果程序任何调用不满足上面的限制，你的程序会被立刻终止并且被判为 **Not correct**。禁止向标准输出中输出和读取标准输入中内容，否则，你的程序会被判为 **Security violation!**。然而你的程序可以向标准错误输出流（`stderr`）中输出。 **警告：提交到洛谷时，您不得包含头文件 `avoid.h`。** 你的源代码必须包含文件 `avoid.h`。为了在本地测试你的程序，你可以将其与 `sample_grader.cpp` 相连接，它可以在「文件-附加文件」中被找到。可以参考后文找到关于样例交互器的描述，并可以看 `sample_grader.cpp` 了解如何将其和你的程序一同运行。

无

无

### 限制和评分 详细子任务限制及分值如下表所示。 | 子任务 | 限制 | 分值 | | :----: | :----------------------------------: | :--: | | $1$ | $R=10,H=1$，并且两位主席位于同一位置 | $10$ | | $2$ | $R=H=20$ | $5$ | | $3$ | $R=30,H=2$ | $10$ | | $4$ | $R=75,H=1$ | $75$ | 对于子任务 $4$，你的实际得分取决于这个子任务的每组测试数据中你送出的最大机器人数 $r_{\max}$，具体取决于以下分段线性函数：  特别地，为了拿到满分，你在最后一个子任务的所有测试点中不能调用 `send` 函数超过 $26$ 次。 ### 样例交互 考虑一个 $R=75,H=20$ 的测试点，主席位于位置 $13$ 和 $37$。首先，交互器会调用 `scout(75, 20)`。然后，你的程序和交互器的交互过程可能如下所示： | 你的程序 | 返回值 | 解释 | | :------------------: | :---------: | -------------------------------------------------------- | | `send({42, 13, 37})` | - | 向位置 $13,37,42$ 送出一个机器人 | | `send({47, 11})` | - | 向位置 $11,47$ 送出一个机器人 | | `wait()` | `{1, 0}` | 等待一小时让机器人返回；只有第一个机器人探测到了一位主席 | | `send({42})` | - | 向位置 $42$ 送出一个机器人 | | `wait()` | `{0}` | 等待一小时；位置 $42$ 没有主席 | | `return {13, 37}` | - | 你确信主席位于位置 $13$ 和 $37$，这个答案是正确的 | 返回 `{37, 13}` 也是可以接受的。注意上述询问显然对于确定主席的位置是不充分的：比如两个主席都在位置 $37$，或者一位主席在 $37$，另一位在 $100$ 都是符合 `wait()` 的返回值的，所以交互器也可能将其判为错误。 ### 交互器 样例交互器首先需要从标准输入中读取两个整数 $R,H$ 和主席位置 $a,b\ (1\le a,b\le 1\ 000)$。然后，交互器调用 `scout(R, H)` 并将所有交互器函数的调用过程输出到标准输出中。当程序终止时，它会输出如下信息之一到标准输出： - **Invalid input.**：交互器通过标准输入读到的输入不是如上述格式的。 - **Invalid send.**：你使用了非法的参数调用 `send` 函数。 - **Out of robots.**：你调用了 `send` 函数超过 $R$ 次。 - **Out of time.**：你调用了 `wait` 函数超过 $H$ 次。 - **Wrong answer.**：`scout` 函数返回的位置不是主席所在的位置。 - **Correct: $r$ robot(s) used, $h$ hour(s) passed.**：`scout` 函数返回的位置正确，调用了 $r$ 次 `send` 和 $h$ 次 `wait`。 相反地，实际测评你的程序使用的交互器只会输出 **Not correct**（对于上述任何错误），**Security violation!** 或者 **Correct: $r$ robot(s) used, $h$ hour(s) passed.**。此外交互器是**适应性**的，即，主席的位置可能取决于你的程序现在或之前的行为。样例交互器和实际使用的交互器会在任何上述错误出现的时候停止你的程序。