由于配置限制，本题只允许使用 C++ 进行提交，且评分方式进行修改（但是我们会将 C/Java/Python 的工程文件放在文件下载区供选手参考）。此外，本题工程文件编译时间较长，请耐心等待，且不要滥用评测资源~

时间限制： 8.0 秒

空间限制： 1024 MB

题目背景

算力调度（Computing Power Scheduling）是指在分布式、多计算节点的计算环境中，基于任务的优先级、资源需求、实时负载等因素，动态调配计算资源以达到最佳系统性能和资源利用效率的过程。算力调度技术的核心在于通过智能算法将算力资源高效地分配给需要处理的任务，避免资源闲置或过载。广泛应用于云计算、大数据处理、边缘计算、人工智能模型训练等领域，是现代信息技术体系中至关重要的组成部分。

随着计算需求的多样化和海量数据的增长，算力调度的应用场景从传统的服务器集群扩展到分布式计算网络、边缘计算环境及 AI 计算平台。例如，在智能制造中，通过算力调度技术实现跨地域计算资源的优化调度，以提升生产效率和降低成本。此外，在自动驾驶汽车的研发中，算力调度能够有效管理和分配大量的传感器数据处理任务，确保实时性和准确性。

题目描述

中关村文理学院顺应人工智能时代，在国家一系列政策的支持下建立了 AI 计算平台，向同学们提供免费的 AI 算力服务，现在作为文理学院计算中心的工作人员，你需要在计算中心的主机上实现一个调度程序，响应同学们的算力需求。

每一个任务有不同的算力需求及内存消耗，为了简化问题，我们假设计算中心总共有 $n$ 个进程可供调度（即最多 可同时运行 $n$ 个任务），且共有 $k$ 张算力相等的显卡，以及总大小为 $m$ GB 的共享内存。算力调度只能以小时为单位，每一个任务 $i$ 所需时间均为整小时，需要 $k_i$ 张显卡，$m_i$ GB 的共享内存，且具有多个 checkpoint（具体数量未知），相邻两个 checkpoint 之间均需要 $t_i$ 小时。其中 $n,m,k,k_i,m_i,t_i$ 均为正整数，进程编号从 $0$ 到 $n-1$，任务编号均为从 $1$ 开始递增的正整数。

由于不同同学对算力需求的紧迫程度不同，你需要根据不同需求灵活调度，具体而言，对于每一个任务 $i$，有一个 重要性 $W_i$，调度的目标是最小化 $\sum W_i\times\frac{T_i}{t_i\times c_i}$，其中 $T_i$ 为第 $i$ 个任务从任务发出到最终运算完成的总时长，$c_i$ 是第 $i$ 个任务的 checkpoint 个数（任务开始时未知）。为了更好地完成任务调度工作，进程调度中允许抢占。

关于 checkpoint 和抢占，值得注意的是本题的特殊要求：

• 一个任务开始的时间是第一个 checkpoint，任务结束的时间不算⼀个 checkpoint，因此有 $c_i$ 个 checkpoint，相邻两个 checkpoint 之间均需要 $t_i$ 小时的任务的总时长 $c_i\times t_i$（实际问题中一个任务可能在最后一个 checkpoint 之后，$t_i$ 小时之前的任一时刻结束，但我们在题目中做了简化，一个任务的结束时间一定是最后一个 checkpoint 之后的第 $t_i$ 小时，因此任务的总时长是 $c_i\times t_i$）。
• 一个任务每个 checkpoint 所需用时是已知的，但是 checkpoint 的总个数对你是未知的，评测系统将会在一个任务完全结束时通知你。
• 若你决定抢占一个任务，在本题中假设抢占不会消耗时间，但会丢失从该任务上个 checkpoint 至今的所有进度。

具体而言，评测采用交互式系统设计，采用事件驱动的方式，交互式系统仅会在事件到来时调用你的调度程序。但是你可以通过调用系统提供的函数向交互式系统主动预约一个特殊的“调度”事件，在这个事件发生的时间点，系统也会调用你的调度程序使你的调度程序可以进行调度。

总共有四种事件，如下所示：

1. 一个任务运行至一个 checkpoint
2. 一个任务完全结束
3. 一个新的任务到达
4. 一个你预约的“调度”事件发生

交互式系统将会在每个事件发生时调用 Event 函数告知你的程序，同一时间发生的多个事件可能会在多个 Event 函数中分别进行告知，你可以在 Event 函数中调用 Schedule 函数进行任务的分配或抢占，或是调用 Appoint 函数预约一个未来的“调度”事件。

形式化地说，系统会先调用 Init 函数告知你的程序进程数 $n$，显卡数量 $k$，共享内存总大小 $m$ GB，以及允许你的程序进行初始化。以下函数中所有时间均以小时为单位。

Init(process_cnt: int, gpu_cnt: int, memory_sum: int)

对于一个任务，系统将会使用以下结构体进行描述：

struct task_info {
    task_id: int
    gpu_demand: int
    memory_demand: int
    per_checkpoint_time: int
    significance: int
};

对于一个事件，系统将会使用以下结构体进行描述：

其中 event_type 取值为 $1\sim 4$，分别依次对应前面提到的四种事件；process_id 和 task_id 用于描述前两种事件；task 成员用于描述第三种事件。

struct event_info {
    event_type: int
    process_id: int
    task_id: int
    task: task_info
};

接下来，系统将会在事件发生时调用以下的 Event 函数。

Event(now_time: int, event: event_info)

你可以在你实现的 Event 函数中调用如下的 Schedule 函数来进行任务调度，调度时间与 Event 函数传入的时间相同。

在调用时需要 task_id 对应的进程所需要的显卡数和内存大小能够被满足（在可能抢占后不多于当前空闲的显卡数和内存大小）。若 process_id 对应的进程正在空闲，则会直接执行 task_id 对应的任务，否则将会先对 process_id 对应的进程中正在进行的任务进行抢占，再执行 task_id 对应的任务。

Schedule(task_id: int, process_id: int)

除此之外，你还可以调用如下的 Appoint 函数来预约⼀个“调度”事件，需要 appoint_time 大于等于当前时间，即 now_time。

Appoint(appoint_time: int)

2 4 16
2
0 1 2 8 3 10 2
1 2 3 10 2 5 3

Objective: 19.1667

样例 1 解释

在本样例中：

• $n=2,k=4,m=16$
• 一共有两个任务
• 第一个任务的出发时间为 0，task_info 为 {1,2,8,3,10}，共 2 个 checkpoint
• 第二个任务的发出时间为 1，task_info 为 {2,3,10,2,5}，共 3 个 checkpoint

所有 task_info 结构体里的参数都对选手的程序可见，只有 checkpoint 的数量是选手的程序不可见的。

不难看出两个任务不能同时运行，我们可以先等 task 1 完整运行完，再在 task 1 跑完后（6 小时时）开始运行 task 2，这样做的目标结果为 19.1667。具体的调度方式如下：

time 0: Schedule(1, 0)
time 6: Schedule(2, 0)

在样例的情况下是可以不需要调用 Appoint() 函数的，因为交互式系统会在 time 6 时触发 Event() 函数通知调度程序 task 1 已经完成，调度程序可以在此时选择开始运行 task 2。

注意事项

请注意，根据问题本身的要求以及交互式系统的设计，你的程序显然必须实现⼀个在线的算法，根据交互式系统的实时反馈情况来进行调度，在调度时，对后续的任务请求是完全未知的。

此外，在调用 Schedule 和 Appoint 函数时，请严格保证调用是合法的，即：

• 在调用 Schedule() 时，请确保 task_id 对应的任务没有正在运行在别的进程上，即它应该还没有被运行过或已经被别的任务抢占。
• 在调用 Schedule() 时，请确保 task_id 对应的任务所需要的显卡数和内存大小能够被满足（在可能抢占后不多于当前空闲的显卡数和内存大小），并且 process_id 在 $0$ 到 $n-1$ 范围内。
• 在调用 Appoint() 时，请确保 appoint_time 大于等于当前时间，即 now_time。

评分方式

本评测链接的计算方式相较于实际比赛有所调整。

对于每个测试点，结果无法正确完成全部进程的掉地得 $0$ 分，正确完成全部调度则获得 $100$ 的正确分。假设选手程序输出的调度权重为 $x$，基线算法的调度权重为 $y$，那么该测试点的性能分为 $\frac{y}{x}\times 0.95\times 200$，超过 $200$ 的按 $200$ 计。对于输出结果符合要求的数据，其得分为正确分与性能分的总和。

子任务

为了方便选手调试程序和测试性能，我们在下发的程序包中为选手提供了 10 组调试数据，其中 5 组与上述真实情况的数据来源一致，另外 5 组则与上述理想情况分布一致。

本评测窗口直接采用这 10 组调试样例进行评分，因此分数仅供参考。

对于所有数据，保证进程数 $n\le 1000$。

测试点编号	任务数量级
$1\sim 4$	$500$
$5\sim 6$	$1000$
$7\sim 8$	$5000$
$9\sim 10$	$10000$

工程文件下载

对于 C++，我们提供了 main.cpp 作为交互工具，选手需要实现 solution.cpp。选手只需要提交 solution.cpp。更多请参照下发文件包中的 TaskSchedule_cpp 目录。其他语言类似。

• 白盒测试样例
• C++ 工程文件
• C 工程文件
• Java 工程文件
• Python 工程文件