注意

请使用 C++ 17 或以上标准提交本题。

题目描述

题目译自 CEOI 2023 Day1 T1「A Light Inconvenience」

今年 CEOI 的科学委员会正在开幕上休息。题已经准备好了，测评系统的 $10^{12}$ 个防火墙也设置好了，委员会成员们正期待着一场精彩的火炬表演。没有什么会出错。除了……没人给这些火炬买了足够的油！现在委员会需要给表演帮忙，以免火炬用光了准备的油。

在表演中，会有一些演员站成一行，从左到右从 $1$ 开始编号。演员的数量随时间而变化。每位演员举着一个火炬，在每个时间点，火炬可能是点燃的，也可能是没点燃的。最初，只有一位演员的火炬是点燃的。

这场表演分为 $Q$ 幕。在第 $a$ 幕的开始，要么 $p_a>0$ 位演员决定从右边加入队列，要么最右边 $p_a>0$ 位演员决定离开。这是不受委员会控制的。最左边的演员总是在台上。加入队列的演员的火炬没有点燃，如果离开的演员的火炬是点燃的，他们会熄灭它。

第 $a$ 幕表演的演员准备一就绪，委员会就需要宣布一个数 $t_a\ge 0$。然后，每个火炬点燃的演员需要把火传给他右边的 $t_a$ 位演员。这意味着演员 $i$ 的火炬会被点燃，当且仅当在这之前演员 $\max\{i-t_a,1\},\ldots,i$ 中至少有一位演员的火炬是点燃的。为了让演出更加动态，$t_a$ 不能大于 $5p_a$，并且应该尽可能小（参考下文「评分」一节）。

在每一幕最后，委员会需要告诉每位火炬点燃的演员是否熄灭他的火炬。出于美观原因，在此之后最右边的演员的火炬需要总是点燃的。此外，为了节约油，剩余点燃的火炬数不能超过 150。

写一个程序告诉委员会应该如何在限制下让表演进行。

交互过程

这是一道交互题。你必须实现如下三个函数：

• void prepare() 在程序开头调用。你可以利用这个函数进行初始设置（或者什么都不做）。
• std::pair<long long, std::vector<long long>> join(long long); 当 $p_a>0$ 位演出者从右边加入队列的时候被调用。这个函数必须返回一个包含委员会宣布的 $t_a$ 和在这一幕最后需要保持火炬点燃的演员列表组成的 pair。这个列表必须按严格递增顺序排列。
• std::pair<long long, std::vector<long long>> leave(long long); 当最右边 $p_a>0$ 位演出者离开队列的时候被调用。再次，这个函数必须返回一个包含委员会宣布的 $t_a$ 和在这一幕最后需要保持火炬点燃的演员列表组成的 pair。这个列表也必须按严格递增顺序排列。

对于每个测试点，如果程序任何返回值不满足上面的限制，你的程序会被立刻终止并且被判为 Not correct。禁止向标准输出中输出和读取标准输入中内容，否则，你的程序会被判为 Security violation!。然而你的程序可以向标准错误输出流（stderr）中输出。

你的源代码必须包含文件 light.h。为了在本地测试你的程序，你可以将其与 sample_grader.cpp 相连接，它可以在「文件-附加文件」中被找到。可以参考后文找到关于样例交互器的描述，并可以看 sample_grader.cpp 了解如何将其和你的程序一同运行。

限制和评分

令 $N$ 表示在任意时刻连续站成一排的演员人数的最大值。对于所有数据，$N\le 10^{17},1\le Q\le 50\ 000$。

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	每个测试点只有一次对 leave 的调用	$5$
$2$	$N\le 700$
$3$	$N\le 5\ 000$	$10$
$4$	$N\le 25\ 000$	$5$
$5$	$N\le 10^5$	$10$
$6$	$N\le 5\times 10^5$	$5$
$7$	无附加限制	$60$

在子任务 $7$ 中，你的实际得分取决于所有幕 $a$ 中 $t_a/p_a$ 的最大值，如下表所示。

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

实际上，为了获得满分，所有 join 和 leave 中返回值必须满足 $t_a\le p_a$。

样例交互

考虑一个 $Q=4$ 的测试点。这里，你的程序和交互器之间的交互过程可能如下所示：

调用	返回值	解释
prepare()	-	你可以在这里做任意的初始化操作（或者什么都不做） 开幕式以一位拿着点燃火炬的演员开始。
join(3)	3, {2, 4}	三位演员加入，现在总共有四位演员 演员 $1$ 点燃演员 $2,3,4$ 的火炬；之后演员 $1$ 和 $3$ 熄灭他们的火炬
leave(2)	0, {2}	最后边两位演员离开（只剩两位演员） 没有新的火炬被点燃；演员 $2$ 的火炬保持点燃
join(2)	3, {2, 4}	两位演员加入，现在总共有四位演员 演员 $2$ 点燃演员 $3,4$ 的火炬；之后演员 $3$ 熄灭他的火炬
join(3)	3, {2, 4, 7}	三位演员加入，现在总共有七位演员 首先演员 $3,5,6,7$ 的火炬被点燃；之后演员 $3,5,6$ 再次熄灭他们的火炬

请注意，上述 join 和 leave 的调用序列在任何子任务中都是合法的。

交互器

样例交互器首先需要从标准输入中读取一个整数 $Q$。然后它会将所有三个函数的调用过程输出到标准输出中。

最开始，交互器会调用 prepare() 函数。然后它会模拟 $Q$ 幕。对于每一幕 $a$，它需要从标准输入中读取一个整数，要么是 $p_a>0$ 表示 $p_a$ 位演员加入队列，要么是 $q_a<0$ 表示 $p_a:=-q_a$ 位演员从队列中离开；然后它会分别调用 join(p_a) 或者 leave(p_a)。

每当停止，交互器会输出如下信息之一到标准输出：

• Invalid input.：交互器从标准输入中读取的输入不是上述形式的。
• The stage is empty.：剩余少于一位演员。
• Invalid return value.：返回值 $t_a$ 不满足 $0\le t_a\le 5p_a$，演员列表没有按照严格递增的顺序排列，或者演员列表中包含小于 $1$ 或大于台上演员数的整数。
• Too many burning torches.：在这一幕之后有多于 $150$ 个火炬是点燃的。
• Rightmost torch not on fire.：最右端的火炬没有点燃，或者它被熄灭了。
• Not all announced torches have been lit.：你的函数返回的演员中至少有一个火炬没有被点燃。
• Correct: ratio at most f, at most b burning torches.：上述错误都没有发生，所有 leave 和 join 函数满足 $t_a\le f\cdot p_a$（四舍五入），在每一幕最后最多有 $b$ 个火炬是点燃的。

相反地，实际使用的交互器只会输出 Not correct（对于任意上面的错误），Security violation!，Partially correct 或者 Correct。此外，交互器是适应性的，即，每一幕中加入或退出的表演者人数可能取决于程序在当前和之前运行中的情况。只要出现上述错误之一，交互器都会自动终止程序。