AI007. Prefix Cache 调度器

# 逐槽位算最长公共前缀,比较键=(-前缀长,负载,编号)取最小;
# 选中后负载加未命中数(请求长−前缀长),缓存序列整体替换为本次请求。
import sys


def lcp(a, b):
    i = 0
    limit = min(len(a), len(b))
    while i < limit and a[i] == b[i]:
        i += 1
    return i


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    at = 0
    s = data[at]; at += 1
    q = data[at]; at += 1
    slots = []
    for _ in range(s):
        load = data[at]; at += 1
        length = data[at]; at += 1
        seq = data[at:at + length]; at += length
        slots.append([load, seq])
    ans = []
    for _ in range(q):
        length = data[at]; at += 1
        req = data[at:at + length]; at += length
        best = 0
        best_prefix = -1
        for i, (load, seq) in enumerate(slots):
            prefix = lcp(seq, req)
            if prefix > best_prefix or (prefix == best_prefix and (load < slots[best][0] or (load == slots[best][0] and i < best))):
                best = i
                best_prefix = prefix
        ans.append(f"{best + 1} {best_prefix}")
        slots[best][0] += len(req) - best_prefix
        slots[best][1] = req
    print("\n".join(ans))


if __name__ == "__main__":
    solve()