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

时间限制： 5.0 秒

空间限制： 4096 MB 1024 MB

题目背景

IaaS（Infrastructure-as-a-Service，基础设施即服务）是云计算领域的主要商业模式之一。在这种模式下，云计算服务提供商将基础设施（包括服务器、存储设备、网络设备等硬件资源）提供给用户，用户可以通过网络（如互联网）来租赁和使用这些基础设施，就像使用自己的数据中心一样，不过这些硬件设备是由云服务提供商负责维护和管理。

在计算资源维度，用户向云计算服务提供商请求虚拟机，每次请求需要云计算服务提供商尽快寻找到一台合适的物理主机，分配相应的 VCPU 核及内存用于创建虚拟机，然后将虚拟机移交给用户，用户可以在满足自身的使用需求后选择释放虚拟机，以降低使用成本。当云计算服务商的整体空闲计算资源较少时，可以通过增加新的物理主机（称为扩容）的方式提高服务能力，保证用户的虚拟机创建请求尽可能地被满足。

题目描述

给定初始物理主机数量和配置 $n,c,m$，表示初始有 $n$ 台主机，每台主机均有 $c$ 个 VCPU 和 $m$ GB 内存。这些物理主机的编号为整数 $0$ 到 $n-1$。用户请求虚拟机以及云服务提供方放置虚拟机的过程可以由一个交互式系统表示，该交互式系统每次由系统调用如下函数中的一种：

1. CREATE <id> <vcpu> <mem>：表示新建一个编号为 <id>、占据 <vcpu> 核、<mem> GB 内存的虚拟机。该指令对应一个函数，相应的输入信息由函数的参数列表传入，需要选手返回给系统在编号为 <machine_id> 的机器上创建该虚拟机。如果需要扩容，那么选手还需返回扩容台数（不扩容返回 $0$），约定系统收到该函数的返回值后总是先新增对应台数的新物理主机，然后再进行虚拟机创建，这些新增物理主机的编号在当前物理主机的编号上依次递增。
2. REMOVE <id>：表示删除编号 <id> 的虚拟机，调用该函数时，系统已经自动删除该虚拟机了。该指令对应一个函数，选手设计的算法在收到该指令后可以进行相应的操作，不需要返回任何信息给系统。

注意：本题目要求选手给出的是在线算法，即选手每次决定在哪一台物理主机上创建虚拟机时都对后续请求未知。

在本题中，我们有如下假定：

1. 虚拟机请求的 VCPU 数 $c$ 满足 $1\le c\le 32$，内存 $m$ GB满足 $1\le m\le 128$。
2. 保证每个虚拟机需要的 VCPU 核数和内存均小于等于单个物理主机的资源量。
3. 初始物理主机数量 $n$ 取值范围为 $[1,5]$，每次可扩容台数为 $[0,100]$，扩容后总物理主机台数不超过 $10^5$，超过时调度过程立即中止，扩容时新增的物理主机 VCPU 核数与内存量与初始的主机一致。
4. CREATE 数量至多为 $5\times 10^4$，对应虚拟机 <id> 一定从 $0$ 开始编号，依次增加；REMOVE 操作只会涉及已经被创建且还未被删除过的虚拟机。
5. 物理主机 VCPU 数 $c$ 满足 $32\le c\le 200$，内存 $m$ GB 满足 $128\le m\le 512$。
6. 如果在某个时刻出现了不合法的操作（创建虚拟机至不存在主机、剩余资源不足等），那么调度过程立即中止。

其他要求：

1. CREATE 函数返回值必须合法，即选择放入的物理主机中剩余的 VCPU 核数与内存均需大于等于当前待创建虚拟机所需的核数与内存。
2. 除了 CREATE/REMOVE 函数外，选手还需要实现 INIT <n> <c> <m> 函数，表示初始化 $n$ 台全空的主机，每台有 $c$ 个 VCPU 和 $m$ GB 内存。

评分方式

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

对于每个测试点，无法正确完成全部调度得 $0$ 分，正确完成全部调度则获得 $100$ 的正确分。假设当前算法以 $x$ 台主机完成了全部调度，基线算法以 $y$ 台主机完成了全部调度，那么该测试点的性能分为 $\frac{y}{x}\times 0.6\times 200$，超过 $200$ 的按 $200$ 计。对于正确完成全部调度的数据，其得分为正确分与性能分的总和。

调试样例共 20 组，对选手公开，供选手在本地调试程序使用；本评测窗口直接采用这 20 组调试样例进行评分，因此分数仅供参考。

1 32 128
5
CREATE 0 16 64
CREATE 1 32 32
REMOVE 1
CREATE 2 16 64
CREATE 3 24 48

void

0 0
1 1
void
0 0
1 0

样例 1 解释

注意：上述的输出并不代表针对输入所得到的标准输出，而是代表每次调用函数之后的返回结果。

1. 测试开始时有一台 32 核 128 GB 物理机主机，编号为 0；调用 INIT 函数，不需要返回任何信息（此处记录为 void）；
2. 该测试集共有 5 条指令需要处理，此信息仅供测试系统使用，不调用任何调度函数；
3. 第 1 条 CREATE 指令创建了编号为 0、消耗 16 核 64 GB 内存的虚拟机，调用 CREATE 函数，返回在 0 号物理主机上放置该虚拟机，放置后不需要扩容。放置完后的物理主机空闲资源的状态为 {(16,64)}。
4. 第 2 条 CREATE 指令创建了编号为 1、消耗 32 核 32 GB 内存的虚拟机，函数返回需扩容 1 台新物理主机（编号为 1），并在该物理主机上放置该虚拟机。放置完后的物理主机空闲资源的状态为 {(16,64),(0,96)}。
5. 第 3 条 REMOVE 指令删除了编号为 1 的虚拟机，调用 REMOVE 函数，不需要返回任何信息（此处记录为 void）。该条指令后物理主机空闲资源的状态为 {(16,64),(32,128)}。
6. 第 4 条 CREATE 指令创建了编号为 2、消耗 16 核 64 GB 内存的虚拟机，函数返回在 0 号物理主机上放置该虚拟机，放置后不需要扩容。放置完后的物理主机空闲资源的状态为 {(0,0),(32,128)}。
7. 第 5 条 CREATE 指令创建了编号为 3、消耗 24 核 48 GB 内存的虚拟机，函数返回在 1 号物理主机上放置该虚拟机，放置后不需要扩容。放置完后的物理主机空闲资源的状态为 {(0,0),(8,80)}。
8. 调度完成，该算法最终通过 2 台物理主机满足了整个调度过程。

答题接口

对 C++，选手需要完成 scheduler.cpp，测试时 scheduler.cpp 将会被替换为选手的代码，其它部分不变。其他三种语言需要完成的部分分别在 scheduler.h，scheduler.py 和 scheduler.java。

对 C++，选手完成 scheduler.cpp 后用本地的 main.cpp 进行调试，也可基于 main.cpp 自行编写测试程序帮助调试，最终只需提交 scheduler.cpp 即可。其他三种语言的调试和提交方式类似。

注意：作为在线算法，scheduler 程序不能直接访问测试数据。

工程文件下载

代码内的中文注释在查看时可能存在乱码，请使用 UTF-8 编码方式打开文件。

• C++ 工程文件
• C 工程文件
• Java 工程文件
• Python 工程文件