题目来自 CCSP2026 T4，评测使用官方数据。我们承认原始题面、大样例、官方数据版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

本题复原了场上选手在各子任务的最佳性能分。由于判分系统需要，本题实际得分为本题原本得分的 5 倍，仅需正确完成调度即视为通过本题。

时间限制： 10.0 秒

空间限制： 512 MB

相关文件： down.zip

这是一道交互题。

题目描述

某大语言模型（LLM）需要同时处理多个文本生成请求。每个请求先提供一段输入，再由模型根据这段输入生成规定数量的 token（文本处理的基本单位）。模型为一个请求生成下一个 token 的过程称为一次“解码”。

解码依赖 Key-Value Cache（KV 缓存）。GPU 的缓存空间以固定大小的缓存块为单位分配和回收。下文将“缓存块”简称为“块”。每块最多容纳 $S$ 个 token 对应的 KV 缓存；即使没有装满，也会占用一整块空间。GPU 最多同时容纳 $C$ 个块。

一个请求的缓存由共享块和私有块组成。每个共享块一定装满，对应 $S$ 个输入 token，可以由多个请求共同使用，在 GPU 中只占一块空间。请求其余的输入 token 和后来生成的 token 存放在自己的私有块中，不与其他请求共用。

请你编写一个完整的在线缓存管理程序，按顺序处理评测程序发来的命令。解码请求由评测程序指定，你只决定如何回收缓存。

为了比较不同回收方案，本题用“逻辑时间”计量开销。你的目标是使累计逻辑时间尽可能小。完整计时规则见“缓存与请求”的第 5 节。

命令与回复格式

每个测试点开始时，GPU 为空，逻辑时间为 0。评测程序先发送一行 S C q，分别表示每块容纳的 token 数、GPU 可容纳的块数和命令数，随后逐行发送 $q$ 条命令。

以下四类命令只需更新状态，无需回复：

CREATE_BLOCK block_id
DROP_BLOCK block_id
ADD id k block_1 ... block_k p m
CANCEL id

• CREATE_BLOCK：创建编号为 block_id 的共享块记录，该块初始位于 GPU 外。
• DROP_BLOCK：删除共享块 block_id。输入保证该共享块已创建、尚未删除，且没有未终止请求引用它。若它仍在 GPU 中，同时释放所占空间。删除后不能再引用。
• ADD：加入编号为 id 的请求。k 是引用的共享块数，后接 k 个互异的共享块编号，再给出输入 token 数 p 和需生成的 token 数 m。这些共享块均已创建且未删除。k=0 时写作 ADD id 0 p m。
• CANCEL：取消编号为 id 的请求。输入保证该请求已通过 ADD 加入。若请求已完成或已取消，不作改变。否则，该请求不再参与解码。若取消前正在运行，系统同时释放其全部私有块。共享块不自动释放。

CREATE_BLOCK 和 ADD 都不分配 GPU 空间。共享块的状态和引用计数更新见“缓存与请求”的第 3 节。

每条解码命令的格式为：

DECODE n id_1 ... id_n

n 表示本轮请求数，后接 n 个互异的请求编号，构成本轮固定批次。这些请求均处于 WAITING 或 RUNNING 状态，请求状态的含义见“缓存与请求”的第 2 节。

请求首次参与 DECODE 时，系统装入所需但尚未驻留的共享块，并分配足够的私有块，所需块数见“缓存与请求”的第 1 节。请求完成后，系统自动释放其全部私有块。空闲共享块不会自动释放，仍留在 GPU 中，直到被驱逐或删除。

收到每条 DECODE 后，你的程序先计算本轮还需要多少块空间。若空间不足，可以驱逐空闲共享块，或抢占本轮批次之外的运行请求。批内请求及其驻留缓存均受到保护。本轮所需空间和回收动作的合法条件，分别见“回收与解码规则”的第 1、2 节。

随后，你的程序必须输出一行回收方案并刷新：

EVICT e action_1 action_2 ... action_e

e 是非负整数，表示回收动作数。动作按输出顺序执行：

• B<block_id>：驱逐指定共享块。
• R<id>：抢占指定请求。抢占和恢复的规则见“缓存与请求”的第 4 节。

输出时，字母与编号之间不加空格，也不写尖括号。例如，B10 表示驱逐共享块 10，R3 表示抢占请求 3。

方案通过验证后，评测程序依次执行回收动作、装入缺少的共享块、分配所需私有块，再让批内每个请求生成一个 token。你的程序也需要按相同规则更新本地状态后，再处理下一条命令。完整执行顺序见“回收与解码规则”的第 3 节。各项操作的计时规则见“缓存与请求”的第 5 节。命令的发送和回复时机见“交互方式”。

缓存与请求

1. 请求缓存的组成

对 ADD 加入的请求，p 为输入 token 数，m 为需生成 token 数，k 为引用的共享块数。令 g 为已生成 token 数，初始为 0。请求缓存分为：

• 共享部分：k 个互异的共享块，每块有唯一编号 block_id，对应 S 个输入 token，可被多个请求引用。
• 私有部分：只属于该请求，没有 block_id，保存其余输入 token 和已生成 token。

因此 $k\times S\le p$，请求当前的私有 token 数和所需私有块数为：

$$\begin{aligned} \mathrm{private\_tokens}&=p-k\times S+g\\ \mathrm{private\_blocks}&=\left\lceil\frac{\mathrm{private\_tokens}}{S}\right\rceil \end{aligned}$$

其中，$\lceil x\rceil$ 表示向上取整。块未装满也占一块，两类块不能转换。同一共享块只计一块，而私有块按请求分别计算。

2. 请求状态与 GPU 占用

ADD 加入的请求初始为 WAITING。参与解码时，所需块进入 GPU 后，请求转为 RUNNING。状态转换如下，生成任务尚未完成的请求在解码后仍为 RUNNING。

请求状态	含义
WAITING	不占用私有块，解码时装入缺失共享块并分配私有块。
RUNNING	当前所需的共享块和私有块均在 GPU 中。
FINISHED	已生成规定数量的 token，为终止状态。
CANCELLED	已取消，为终止状态。

RUNNING 请求占用上式所算的私有块。WAITING 请求不占用私有块，参与解码时分配私有块。块在 GPU 中称为“驻留”，驱逐或释放后即可腾出空间。

3. 共享块状态

每个共享块有两个引用计数：live 是引用该块的未终止请求数，active 是引用该块的 RUNNING 请求数。共享块的状态如下：

共享块状态	含义	GPU 占用
ABSENT	已创建，但不在 GPU 中。	0 块
IDLE	驻留于 GPU，且 active = 0。	1 块
ACTIVE	驻留于 GPU，且 active > 0。

驻留共享块的 active 降为 0 时转为 IDLE，但不自动释放。GPU 已用块数等于驻留共享块与所有 RUNNING 请求私有块的总数。

执行 ADD 时，相关共享块的 live 各加 1。WAITING 请求进入 RUNNING 时，active 各加 1，抢占时各减 1。请求完成或取消时，live 各减 1。若此前正在运行，active 也各减 1。

4. 抢占与请求恢复

抢占一个本轮批次之外的 RUNNING 请求时，依次执行：

1. 释放该请求的全部私有块。
2. 将请求改为 WAITING，保留已生成 token 数 g。
3. 将其引用的每个共享块的 active 减少 1，计数降为 0 的驻留共享块变为 IDLE。

抢占后请求仍未终止，因此 live 不变，其引用的共享块也不会随之释放。

WAITING 请求被指定解码时，系统需要先装入其尚未驻留的共享块，并为它分配所需的私有块。对首次解码的新请求，这是第一次分配私有块。对被抢占后恢复的请求，则需要重新分配私有块。仍驻留在 GPU 中的共享块可直接复用，同一轮中同一个未驻留共享块只装入一次。

5. 逻辑时间

逻辑时间初始为 0。将一个 GPU 外的共享块装入 GPU，或为 WAITING 请求分配一个私有块，都会使逻辑时间增加 1。每成功执行一条 DECODE，逻辑时间增加 1，无论该批次包含多少个请求。首次分配与抢占后的重新分配采用相同的计时方式。

为容纳新生成的 token 而分配私有块，不增加逻辑时间。驱逐、抢占、请求终止时的缓存释放以及其他输入命令也不计时。

回收与解码规则

1. 固定批次与新增空间

选手不能增删批内请求。回收期间，批内请求及其全部驻留缓存均受到保护：不能抢占批内请求、释放其私有块或驱逐其引用的驻留共享块。

“本轮空间需求”指本轮 DECODE 需要新增的 GPU 块数，已驻留的块不重复计算，包括：

1. 共享块装入数：批内 WAITING 请求引用但是当前不在 GPU 内部（即当前状态为 ABSENT）的共享块数，同一块只计一次。
2. 需分配的私有块数：批内 WAITING 请求所需私有块数之和。
3. 需新增的私有块数：批内各请求生成一个 token 时新增的私有块数之和。

计算第 3 项时，比较批内每个请求在本轮生成 token 前后所需的私有块数。每个请求只生成一个 token，因此块数要么不变，要么增加一块。第 3 项就是批内各请求增加的私有块数之和。

2. 输出回收方案

回收方案的格式和两类回收动作见“命令与回复格式”。动作按输出顺序执行，且每个动作必须在执行时合法：

• B<block_id>：指定共享块必须为未受保护的 IDLE 块，驱逐后变为 ABSENT，释放一块空间。
• R<id>：指定请求必须为本轮批次之外的 RUNNING 请求，状态和缓存按前述抢占规则更新。

抢占使共享块变为 IDLE 后，该块仍占用空间。要释放这块空间，还需输出对应的 B<block_id> 将其驱逐。

若当前空闲块数已满足本轮空间需求，必须输出 EVICT 0。否则，应在本地按输出顺序模拟回收动作。空闲块数一旦满足本轮需求，必须结束方案，不能再添加动作。尚未满足时也不能提前结束。

最后一个动作释放的块数可以超过当前缺口。例如还缺两块时，抢占一个占用三块的请求是合法的，但此后不能再添加动作。

数据保证每轮都有合法的回收方案。

3. 一轮解码的执行顺序

评测程序收到合法回收方案后，依次：

1. 按输出顺序执行全部回收动作。
2. 装入缺失共享块，为批内 WAITING 请求分配私有块并改为 RUNNING，相应共享块的 active 各增 1。装入一个共享块或分配一个私有块，逻辑时间均加 1。
3. 若生成本轮 token 会使某个批内请求需要增加私有块，先为该请求分配一个新私有块。
4. 逻辑时间增加 1，批内请求各生成一个 token，其已生成 token 数 $g_i$ 增加 1。
5. 已生成规定数量 token 的请求（即 $g_i=m_i$）按编号从小到大依次结束并清理。

请求完成时转为 FINISHED，释放全部私有块，并使所引用共享块的 active、live 各减 1。驻留块的 active 变为 0 时转为 IDLE。

必须先确保整个批次有足够空间，才能生成 token。生成完毕后，系统释放已完成请求的私有块。因此，即使某个请求会在本轮完成，它完成后释放的空间也不能计入本轮可用空间。

下面用一个完整样例串联上述命令和规则。

4 3 6
CREATE_BLOCK 10
ADD 1 1 10 7 2
ADD 2 1 10 6 2
DECODE 2 1 2
DECODE 1 1
DECODE 1 2

EVICT 0
EVICT 1 R2
EVICT 0

样例 1 解释

首行的 4 3 6 依次表示每个缓存块最多容纳 4 个 token、GPU 最多容纳 3 个缓存块、共有 6 条命令。

建立共享块和请求。前三条命令创建共享块 10 以及请求 1、2。两个请求都引用共享块 10，其私有输入分别有 3 个（7-4）和 2 个（6-4）token，且都需生成 2 个 token。CREATE_BLOCK 和 ADD 均不分配 GPU 空间，因此此时 GPU 仍为空。

执行第 4 条命令。DECODE 2 1 2 中，第一个参数 2 表示批次包含两个请求，后面的 1、2 是请求编号。系统需从 GPU 外装入共享块 10，并为两个 WAITING 请求各分配一个私有块，正好占满 GPU 的 3 个缓存块，无需回收，故输出 EVICT 0。装入和分配使逻辑时间增加 3，本条 DECODE 再增加 1；两个请求各生成一个 token 后，累计逻辑时间为 4。

执行第 5 条命令。本轮只解码请求 1。它再生成一个 token 后需要第二个私有块，但 GPU 已满。请求 1 属于本轮批次，不能被抢占；请求 2 不在本轮批次中，可以抢占并释放其全部私有块，故输出 EVICT 1 R2。请求 1 生成第二个 token 后完成，系统自动释放它的全部私有块。本轮没有共享块装入或 WAITING 请求的私有块分配，只有 DECODE 使逻辑时间增加 1，累计逻辑时间变为 5。

执行第 6 条命令。共享块 10 仍驻留在 GPU 中。请求 2 被抢占时保留了生成进度，因此恢复后共有 3 个私有 token：2 个私有输入 token 和 1 个已生成 token。一个私有块即可容纳这些 token，系统为它重新分配一个私有块，无需回收，故输出 EVICT 0。私有块分配和本条 DECODE 各使逻辑时间增加 1，最终逻辑时间为 7。请求 2 完成后，共享块 10 变为空闲，但仍驻留在 GPU 中。本样例没有后续命令，无需再输出；如果之后的 DECODE 需要腾出空间，可以在回收方案中输出 B10 驱逐该块。

交互方式

评测程序按前述格式逐行发送 $q$ 条命令。

发送 CREATE_BLOCK、DROP_BLOCK、ADD 或 CANCEL 后，评测程序直接发送下一条命令。发送 DECODE 后，评测程序等待本轮回复，再发送下一条命令。程序必须先输出并刷新回复，再读取下一条命令。回复前，下一条命令尚未进入标准输入。提前读取会因双方相互等待而超时。

程序可以保存此前收到的全部信息，但必须处理完 $q$ 条命令，不能因当前请求均已终止而提前退出。余下命令仍可能通过 ADD 加入请求。

输入保证最后每个请求均已完成或取消。处理完命令后正常退出。标准输出只能包含各轮的 EVICT 行，调试信息可写入标准错误。

合法性判定

出现以下任一情况，该测试点判为非法。子任务内任一测试点非法，该子任务得 0 分：

• 程序异常、超时或在处理完命令前退出。
• EVICT 行语法错误、动作数不符、缺少回复，或存在额外标准输出。
• 回收动作指向不存在、受保护或当时类型不合法的对象。
• 空闲空间已足够时仍输出动作，或全部动作执行后仍不能满足本轮空间需求。

评分方式

单个测试点的评价指标是累计逻辑时间 $T$，越小越好：

T = 共享块装入总次数 + 为 WAITING 请求分配的私有块总数 + 成功执行的 DECODE 次数

测试数据按子任务计分，每个测试点均启动新进程。子任务 $G$ 中各测试点的逻辑时间为 $T_j$，总时间为 $T_G=\sum_j T_j$。若该子任务满分为 $W_G$，则得分为：

$$\mathrm{score}_G=W_G\times\left(0.2+0.8\times\frac{T_{\mathrm{best},G}}{T_G}\right)$$

$T_{\mathrm{best},G}$ 是在当前使用的测试数据上，随题基础管理程序和所有已完成评测的提交取得的子任务 $G$ 合法总时间最小值。

各子任务满分 $W_G$ 之和为 $100$，最终成绩为各子任务得分之和，保留六位小数。

比赛使用隐藏测试集。每份提交完成评测后，实时更新 $T_{\mathrm{best},G}$。若出现新的最小值，所有已评测提交的排行榜分数都按新值重新计算。

数据范围

每个测试点至少创建一个不会被 CANCEL 的请求，故合法结果 $T>0$。

$1\le S,C\le10^5$，$1\le q\le2\times10^5$，共享块数、请求数均不超过 $10^5$。编号范围为 $1$ 至 $10^9$，同类编号不重复，共享块与请求可以同号。

每个请求满足 $0\le k\le30$、$0\le p\le10^{12}$、$1\le m\le10^{12}$、$k\times S\le p$，共享块引用总数不超过 $3\times10^5$。每条 DECODE 满足 $1\le n\le10^5$，全部 $n$ 之和不超过 $2\times10^5$，给出的请求编号互异且均未终止。

数据保证每个固定批次都能整体放入 GPU：批次引用的不同共享块数，加上各请求生成本轮 token 后的私有块数之和，不超过 $C$。

子任务

共 10 个子任务，各含 2 个测试点。表中未列出的限制见“数据范围”。

子任务编号	分值	额外限制
1	5	$S=1,\ C=7,\ q=7,\ k=0$
2
3	17	$S\le16,\ C\le96,\ q\le600,\ k\le4,\ n\le6$
4		$S\le32,\ C\le145,\ q\le600,\ k\le2,\ n\le6$
5		$S\le16,\ C\le150,\ q\le10^3,\ k\le3,\ n\le7$
6		$S\le64,\ C\le140,\ q\le600,\ k=0,\ n\le5$
7	10	$q\le400,\ k\le2,\ n\le3$
8	4	$k=0,\ p=0,\ m\le2$
9		请求数不超过 $1$，共享块数不超过 $10^5$，$n\le1$
10		$q\le20030,\ m=1,\ n\le10^4$，共享块引用总数不超过 $3\times10^5$