题目描述

译自 $CEOI$ $2023$ $Day1$ $T1$「$A$ $Light$ $Inconvenience$」。

背景

表演中演员站成一行，从左到右编号为 $1, 2, \ldots$，人数随时间变化。每位演员手持火炬，火炬状态为「点燃」或「熄灭」。初始时，仅最左侧 $1$ 位演员的火炬是点燃的。

表演分为 $Q$ 幕，每幕开始时会发生以下两种事件之一：

1. 右侧加入 $p_a > 0$ 位演员（新加入演员的火炬均为熄灭状态）；
2. 最右侧 $p_a > 0$ 位演员离开（离开的演员若火炬点燃，会自动熄灭）。

事件发生后，委员会需执行以下操作：

1. 宣布一个非负整数 $t_a$，满足 $t_a \leq 5p_a$，且需尽可能小（评分与 $t_a/p_a$ 比值相关）；
2. 火炬传递：点燃的演员会将火传给右侧 $t_a$ 位演员。具体来说，演员 $i$ 的火炬被点燃，当且仅当传递前 $\max\{i-t_a, 1\}, \ldots, i$ 中至少有一位演员的火炬是点燃的；
3. 熄灭控制：宣布需保持点燃的演员列表，需满足：
   • 列表按严格递增顺序排列；
   • 最右侧演员的火炬必须保持点燃；
   • 剩余点燃的火炬数不超过 $150$。

核心任务

实现指定交互函数，在满足所有限制的前提下，完成每幕的 $t_a$ 选择和点燃列表指定。

交互过程

本题为交互题，需实现以下三个函数（源代码必须包含文件 light.h）：

1. void prepare()：程序开头调用，用于初始化（可空实现）；
2. std::pair<long long, std::vector<long long>> join(long long p_a)：
   • 触发条件：右侧加入 $p_a$ 位演员；
   • 返回值：(t_a, 保持点燃的演员列表)，列表需严格递增；
3. std::pair<long long, std::vector<long long>> leave(long long p_a)：
   • 触发条件：最右侧离开 $p_a$ 位演员；
   • 返回值：(t_a, 保持点燃的演员列表)，列表需严格递增。

交互限制

• 禁止读写标准输入/输出（仅可向标准错误流 stderr 输出调试信息）；
• 任何返回值违反限制（如 $t_a > 5p_a$、列表非递增、列表包含无效编号等），程序会立即终止并判为「Not correct」。

限制与评分

数据范围

• 任意时刻演员人数最大值 $N \leq 10^{17}$；
• 幕数 $1 \leq Q \leq 50000$。

子任务评分

子任务编号	附加限制	分值
$1$	仅一次 leave 调用	$5$
$2$	$N \leq 700$	-
$3$	$N \leq 5000$	$10$
$4$	$N \leq 25000$	$5$
$5$	$N \leq 10^5$	$10$
$6$	$N \leq 5 \times 10^5$	$5$
$7$	无附加限制	$60$

子任务 $7$ 评分细则（按 $\max(t_a/p_a)$ 比值）

$\max(t_a/p_a)$ 区间	$[0,1]$	$(1,2]$	$(2,3]$	$(3,5]$
分值	$60$	$35$	$20$	$10$

注：满分要求所有幕的 $t_a \leq p_a$。

样例交互

交互流程（$Q=4$）

调用	返回值	解释
prepare()	-	初始化（无操作）
初始状态		仅演员 $1$ 的火炬点燃
join(3)	$(3, \{2, 4\})$	加入 $3$ 位演员（总人数 $4$）： 1. $t_a=3$，演员 $1$ 点燃 $2,3,4$； 2. 保持点燃 $2,4$（熄灭 $1,3$）
leave(2)	$(0, \{2\})$	离开 $2$ 位演员（总人数 $2$）： 1. $t_a=0$，无新点燃； 2. 保持点燃 $2$（最右侧）
join(2)	$(3, \{2, 4\})$	加入 $2$ 位演员（总人数 $4$）： 1. $t_a=3$，演员 $2$ 点燃 $3,4$； 2. 保持点燃 $2,4$（熄灭 $3$）
join(3)	$(3, \{2, 4, 7\})$	加入 $3$ 位演员（总人数 $7$）： 1. $t_a=3$，演员 $2,4$ 点燃 $3,5,6,7$； 2. 保持点燃 $2,4,7$（熄灭 $3,5,6$）

交互器说明

样例交互器（sample_grader.cpp）

1. 从标准输入读取 $Q$；
2. 调用 prepare()；
3. 对每幕：
   • 读取输入：正数表示 join(p_a)，负数表示 leave(-p_a)；
   • 调用对应函数并验证返回值；
4. 向标准输出输出交互结果（如 Correct、Invalid return value 等）。

实际交互器

仅输出以下结果之一：

• Not correct：违反任何限制；
• Security violation!：读写标准输入/输出；
• Partially correct：部分子任务通过；
• Correct：全部限制满足。