CF927A BuberPool Taxi Optimization

这是一个交互式优化问题。你不需要找到最优解，每个解会根据其效率获得分数。由于本题为交互题，在测试过程中，评测程序和你的程序会通过标准输入输出流交换信息。每次输出信息后，请记得刷新输出缓冲区，以确保信息被完全发送。例如，在 C++ 中可以使用 `fflush(stdout)`，在 Java 中使用 `System.out.flush()`，在 Pascal 中使用 `flush(output)`，在 Python 中使用 `stdout.flush()`。 你的任务是自动化下一代出租车服务 BuberPool。每辆 Buber 汽车最多可同时运送四名乘客。汽车需要前往乘客的位置，接上他们并送到目的地。此外，与传统出租车不同，每辆车可同时处理最多四个订单。例如，在送一名乘客去目的地的途中，汽车可以顺路接另一名乘客，或者绕路送另一名乘客下车。 我们对现实问题采用如下简化的离散模型。 假设城市为一个 $w$ 条街道和 $h$ 条大道组成的矩形网格，共有 $w \times h$ 个路口。街道编号为 $1$ 到 $w$，大道编号为 $1$ 到 $h$。我们只考虑非负整数时刻。所有操作在“时钟滴答”间隔内进行：即连续时刻之间的时间段。在任意时刻，每辆车都位于某个路口 $(x, y)$，其中 $1 \le x \le w$，$1 \le y \le h$。任意数量的车辆可以同时停在同一个路口。在一个时钟滴答内，每辆车可以选择保持在原地，或者将其某一个坐标（街道或大道）增加或减少 $1$。 在时刻 $0$，你会得到 $k$ 辆车的初始位置：$(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$。车辆数量为 $k$，在模拟过程中不会改变。 此外，你的程序会收到乘客的订单。在本题中，每个订单由一名乘客发出，因此每辆车最多可同时处理四个订单。为进一步简化，所有订单的时刻均不相同，且按时间顺序给出。因此，第 $j$ 个订单由五个整数描述：时刻 $t_j$，上车位置 $(sx_j, sy_j)$，下车位置 $(tx_j, ty_j)$。 在时刻 $0$，以及每次收到新订单后，你都可以为车辆下达指令集（具体限制见下文）。每次你可以为任意数量的车辆下达指令集。不同车辆的指令集分别给出。一个指令集是若干三元组 $(cx_1, cy_1, a_1), (cx_2, cy_2, a_2), \ldots, (cx_m, cy_m, a_m)$ 的序列，其中 $m$ 为指令数量。这些数字的含义如下： - 车辆应首先前往 $(cx_1, cy_1)$，然后依次前往 $(cx_2, cy_2), \ldots, (cx_m, cy_m)$。每个 $(cx_i, cy_i)$ 可以是城市中的任意路口，不一定是上下车点。在从一个位置驶向另一个位置时，车辆总是先改变第一个坐标直到等于目标的第一个坐标，然后再改变第二个坐标。因此，从 $(p_1, q_1)$ 到 $(p_2, q_2)$，车辆会先移动 $(p_1, q_1) \rightarrow (p_2, q_1)$，再移动 $(p_2, q_1) \rightarrow (p_2, q_2)$。在每个时钟滴答内，车辆的某一坐标会变化 $1$。 - $a_i$ 的值表示操作类型。如果 $a_i = 0$，车辆仅前往 $(cx_i, cy_i)$，不执行特殊操作。如果 $a_i > 0$，车辆前往 $(cx_i, cy_i)$ 并在此接上编号为 $a_i$ 的乘客（该乘客的上车点应为 $(cx_i, cy_i)$，且乘客仍在等待）。如果 $a_i < 0$，车辆前往 $(cx_i, cy_i)$ 并在此放下编号为 $-a_i$ 的乘客（该乘客的下车点应为 $(cx_i, cy_i)$，且乘客已在车上）。上下车操作是瞬时完成的。 当你为一辆车下达指令集时，其之前的指令集会被新指令集替换。这样，每辆车同一时刻最多只执行一个指令集。如果没有指令，或所有指令已完成，车辆会停在最后一个位置。指令按给定顺序依次执行。 对于每个订单，首先所有车辆会执行当前指令集直到订单时刻到来，然后订单信息会传递给你的程序，之后你可以为部分车辆下达新指令集。未获得新指令集的车辆会继续执行原有指令集。 因此，整体测试流程如下： 1. 你的程序读取城市规模、车辆数量及其初始坐标。 2. 程序输出部分车辆的初始指令集，车辆开始执行指令。 3. 程序读取下一个订单的时刻 $t_j$（若 $t_j = -1$，则应输出最终指令集并正常退出）。 4. 程序读取 $sx_j, sy_j, tx_j, ty_j$，即第 $j$ 个订单的上下车位置。 5. 程序为车辆输出下一步指令集。 6. 回到第 3 步。 在第 3 步程序退出后，所有指令会被完全执行，之后模拟才会结束。 你在每个测试点的得分为所有订单得分的平均值，四舍五入取整。每个订单的得分为 $\alpha \cdot (100 + w_0)$，其中 $w_0$ 是理想情况下订单所需时间，即从 $(sx_j, sy_j)$ 到 $(tx_j, ty_j)$ 的最短距离（$w_0 = |sx_j - tx_j| + |sy_j - ty_j|$），$\alpha$ 是 $0$ 到 $1$ 之间的实数，表示乘客对本次行程的满意度。$\alpha$ 的计算公式如下： $$ \alpha = \frac{10^7 - \min(d_1^2 + d_2^2, 10^7)}{10^7} $$ 其中 $d_1$ 为上车前的等待时间（订单时刻与实际上车时刻之差），$d_2$ 为实际行程时间与理想行程时间的差值（理想行程时间为 $w_0$）。若订单未完成，则 $\alpha = 0$。 你的总得分为所有测试点得分之和。

第一行输入两个整数 $w$ 和 $h$（$300 \le w, h \le 3000$），表示城市的宽度和高度。第二行输入一个整数 $k$（$1 \le k \le 40$），表示车辆数量。接下来 $k$ 行，每行两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le w$，$1 \le y_i \le h$），表示每辆车的初始位置。任意数量的车辆可以位于同一位置。 读入上述数据后，你的程序应输出车辆的初始指令集（见输出格式），然后处理订单。 每个订单占一行，由五个整数 $t_j, sx_j, sy_j, tx_j, ty_j$（$1 \le t_j \le 86\,400$，$1 \le sx_j, tx_j \le w$，$1 \le sy_j, ty_j \le h$）描述，其中 $t_j$ 为订单时刻，$(sx_j, sy_j)$ 为上车点，$(tx_j, ty_j)$ 为下车点。所有订单按严格递增的 $t_j$ 排序，且每个订单的上下车点不同。 所有订单结束后，输入一行五个整数 $-1$。也就是说，如果读入的订单 $t_j = -1$，则表示没有更多订单。保证订单数量在 $1$ 到 $500$ 之间。 每次读入订单后，请为车辆输出指令集。订单全部结束后也要输出一次指令集。因此，若输入包含 $q$ 个订单，则你需要输出 $q+2$ 次车辆指令集（初始一次，每个订单后一次，最后一次）。 请注意，模拟过程实现为：对于每个订单，首先所有车辆会执行当前指令集直到订单时刻到来，然后订单信息传递给你的程序，之后你可以为部分车辆下达新指令集。未获得新指令集的车辆会继续执行原有指令集。 比赛主阶段，你的程序将在 40 个初步测试点上测试。奇数编号的测试点可在此下载：。每种生成方法的测试点中都有一个公开测试。 比赛结束后，最后一个在初步测试点上得分为正的提交会用于最终评测，其他提交会被忽略。所有入选提交将在与初步测试点生成方式相同的隐藏测试点上评测。评测组会尽量保持测试类型和统计参数不变。

（略，详见题目描述）

（无） 由 ChatGPT 4.1 翻译