题目内容

实现一个多节点 LLM 推理集群的请求路由器。每个节点维护一个 KV Cache，缓存已处理请求的完整 token 序列（模拟 prefill 完成后 KV 被缓存）。新请求到来时，选择能复用最多 KV Cache 的节点以减少 prefill 计算量；命中长度相同时，选负载最轻的节点。

背景：在实际 LLM 推理系统中（如 vLLM、SGLang），若新请求的前缀与某节点已缓存的请求存在公共前缀，该部分的 prefill 计算可直接复用，显著降低 TTFT（Time To First Token）。

路由规则（按优先级）：

选与当前请求拥有最长公共前缀（LCP）的节点

若多个节点 LCP 长度相同（含均为 $0$），选当前队列中待处理 token 总量最少的节点

状态更新（每条请求路由后立即执行，模拟 prefill 完成）：

将请求的完整 token 序列加入所选节点的缓存

将请求的 token 数（$len(request)$）累加到所选节点的负载上

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms

内存限制：C/C++ 512MB，其他语言：1024MB

输入描述

Line 1: $N$ $M$ # $N$个节点，$M$个请求

Line 2: $load[0..N-1]$ # 每个节点初始待处理 token 数

Line 3~$N+2$: $K$ $seq_0$ $seq_1$ ... # 每个节点初始缓存：$K$条序列，各序列 token 逗号分隔。$K=0$ 时该行只有 “0”

Line $N+3$~end: $t_0$ $t_1$ $t_2$ ... # 每条请求的 token 序列，空格分隔，共 $M$ 行

输出描述

一行，$M$ 个整数，$assignment[i]$ 为第 $i$ 条请求分配的节点编号（0-indexed）。

样例1

输入：

3 4
100 50 200
0
0
0
10 20 30 40 50
10 20 30 40 60
10 20 30 40 50 70
5 6 7 8

输出：

1 1 1 1

解释：逐步分析：

样例2

输入：

2 4
0 0
1 1,2,3,4,5
0
1 2 3 4 5 6 7
8 9 10 11
1 2 3 4 5 100 200
99 88 77

输出：

0 1 0 1

解释：逐步分析：