CF642A Scheduler for Invokers

在本题中，你需要为测试提交的任务编写一个分发子系统。 “Invoker”（执行器）（简化后）是测试系统的组件，它会对某个提交在单个测试点上进行测试，并返回判定结果。本题中，可能的判定结果只有两种 — OK（测试通过）或 RJ（拒绝，测试未通过）。 任务分发子系统称为“调度器（scheduler）”，你需要实现它。 对于每道题目，会给出两个参数：该题的测试点数量以及题目的时间限制。 我们假设系统按离散时间工作，每一个时钟周期（tick）等于 10 毫秒。如果某个事件发生时刻不是 10ms 的整数倍，则调度器将在下一个最近的时钟周期收到该事件。 在比赛结束（即比赛开始后一周）后，你最后一次提交（得分为正）的代码将会被选中用于最终测试。最终测试为保密测试，与竞赛过程中使用的测试点不同。在最终测试中获得的总分将决定比赛的优胜者。 特别为本轮开发了提交包含多个源文件的 ZIP 压缩包的功能。所有文件应放在 ZIP 根目录下，不得有任何子目录。你可以在以下情况下使用该功能： - Java 8：主程序应位于默认包的 Main 类中； - GNU C++ 11：恰好有一个文件包含入口点 main，所有要编译的文件扩展名为 cpp。 你将在交互模式下接收提交和 invoker 的判定。请确保每次操作后使用流刷新操作，以防止输出缓冲。例如，在 C 或 C++ 中可以使用 "fflush(stdout)"，Java 中可以使用 "System.out.flush()"，Pascal 中可以使用 "flush(output)"。 本题的评分方式如下：设 $a_i$ 是第 $i$ 个提交的完整测试时间（包括等待时间），即从接收到该提交到测试全部完成所经过的时间。计算 $r = \max\limits_{i=1}^{n} a_i$，其中 $n$ 是需要测试的提交总数。单个测试的分数按如下公式计算：$Score = 10^3 \cdot \frac{A}{B}$，其中 $A$ 是由评测者写的一个简单调度器得到的 $r$，$B$ 是你的调度器得到的 $r$。 用于本地测试的材料将在近期发布。相关包将包含交互器和交互器的测试数据集。

程序启动时，你将从标准输入读取以下数据： - 第一行为一个整数 $t$（$1 \leq t \leq 500$）— 可用的 invoker 数量（所有 invoker 可同时、独立地工作，空闲的 invoker 会在被分派任务后立即开始测试）。 - 第二行为一个整数 $p$（$1 \leq p \leq 10000$）— 题目的数量，即预期需要测试提交的题目数量。 接下来 $p$ 行，每行描述一道题目。每行包含该题目的时间限制（为 250 到 30000 之间的整数）和测试点数量（1 到 1000 之间）。 之后的数据为交互输入。即，调度器在输出上一个时钟周期操作信息后，才能读取当前时钟周期的输入。首先，会有一个关于当前时钟周期新提交需要测试的数据块。每个提交对应单独一行为一个整数，表示题目的下标（从 0 到 $p - 1$）。若本周期没有新的提交需测试，则为 $-1$。 接下来，会有一个本周期内 invoker 返回的判定结果的数据块。每一行为三个元素：提交的下标、测试点编号和测试结果（OK 或 RJ）。该数据块以一行 "-1 -1" 结束。 注意：题目和测试点均按照出现顺序从零编号。单一测试中总提交数量不超过 20000。

在读取完下一时钟周期的数据后，你的调度器可以决定发送哪些提交去进行指定的测试点测试。对每个要进行测试的任务，输出一行，包含两个整数：提交下标和测试点编号。若有空闲 invoker，该任务会马上被测试（invoker 变为忙碌状态，直到返回结果）。否则你发送的请求会被忽略。当你完成本周期的分配请求后，输出一行 "-1 -1"。 你可以在程序中直接维护空闲的 invoker 数量，每次分派任务给 invoker 时将变量 $t$ 减 1（若 $t=0$，则无需分派任务），每有一个 invoker 返回结果时将 $t$ 加 1。 若某一提交的所有测试点均已通过测试，或某一测试点得到第一个 RJ 判定后，其余测试点无需继续测试，则认为该提交测试已完成。 当所有计划的提交经测试全部完成后，交互器会终止输入数据流。这时你的程序应当立即停止。

材料和测试数据现已发布，地址为 。请阅读 README.txt，以了解如何使用交互器进行本地测试。 由 ChatGPT 5 翻译