#P5774. 「CEOI2023」A Light Inconvenience

    ID: 10314 交互题 1000ms 512MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-构造与建模序列构造不变量分析模拟与实现技巧坐标变换排序与序列处理同向双指针CF2900CEOI2023

「CEOI2023」A Light Inconvenience

题目描述

今年 CEOI 的开幕式上有一场精彩的火炬表演。表演者们站成一排,从 11 开始从左往右编号。每个表演者举着一根火炬,初始台上只有编号为 11 的表演者,他的火炬已经点燃。

表演分为 QQ 幕。在第 aa 幕开始之前,要么 pa>0p_a > 0 个表演者从右侧加入表演,他们的火炬是熄灭的;要么最右侧 pa>0p_a > 0 个表演者决定离开,并熄灭他们的火炬(如果他们的火炬是点燃的)。表演者的加入和离开不受委员会的控制。最左侧的表演者永远留在台上。

一旦第 aa 幕准备好了,委员会需要宣布一个非负整数 ta≥0t_a \geq 0。对于每个举着点燃的火炬的表演者,用他的火炬点燃他右侧 tat_a 个人的火炬。也就是说,第 ii 个人的火炬在传火后是点燃的,当且仅当表演者 max⁡(1,i−ta),⋯ ,i\max(1, i - t_a), \cdots, i 中至少一个人的火炬在传火前是点燃的。tat_a 不应超过 5pa5p_a,且越小越好。

在第 aa 幕结束时,委员会需要告知每个举着点燃的火炬的表演者是否熄灭火炬。出于美学原因,最右侧的表演者应保持他的火炬点燃。此外,为了节省汽油,点燃的火炬数量不应超过 150150。

编写程序帮助委员会在上述限制下主持表演。

交互格式

你需要实现以下三个函数:

void prepare();

在程序最开始调用。你可以用这个函数做一些预处理,或者什么也不做。

pair<long long, vector<long long>> join(long long p);

当 pa>0p_a > 0 个表演者加入时,这个函数被调用。你需要返回 tat_a 和这一幕结束后所有火炬保持点燃的表演者的编号,编号列表严格升序排列。用 pair 将这两个信息组合在一起。

pair<long long, vector<long long>> leave(long long p);

当最右侧 pa>0p_a > 0 个表演者离开时,这个函数被调用。你需要返回 tat_a 和这一幕结束后所有火炬保持点燃的表演者的编号,编号列表严格升序排列。用 pair 将这两个信息组合在一起。

如果任何返回值不符合限制,你的程序将被立刻终止并被判为不正确。你不应从标准输入流读入任何信息,也不应向标准输出流输出任何信息。但是你可以自由写入标准错误流。

源文件需包含 light.h。你可以将你的程序链接附件中的 sample_grader.cpp 进行本地测试。下方有样例交互库的详细描述。

交互库

样例交互库首先从标准输入流中读入整数 QQ。它会向标准输出流中写入以上三个函数的执行信息。

首先,样例交互库调用 prepare()。接下来它将模拟 QQ 幕。第 aa 幕,交互库将读入一个整数 p>0p > 0 或 q<0q < 0。若读入 p>0p > 0,说明 pp 个表演者加入表演,调用 join(p)。若读入 q<0q < 0,说明最右侧 −q-q 个表演者离开表演,调用 leave(-q)。

在终止程序后,交互库会向标准输出流写入以下信息之一:

  • Invalid input. 标准输入流的输入不符合上述格式。
  • The stage is empty. 少于一个表演者留在台上。
  • Invalid return value. 返回值 tat_a 不满足 0≤ta≤5pa0\leq t_a\leq 5p_a,保持火炬点燃的表演者列表没有升序排列,或列表包含了小于 11 或大于仍在台上的表演者总数的编号。
  • Too many burning torches. 某一幕结束后大于 150150 个火炬保持点燃。
  • Rightmost torch not on fire. 最右侧的表演者的火炬没有点燃。
  • Not all announced torches have been lit. 你的程序要求保持点燃的火炬在此之前没有被点燃。
  • Correct: ratio at most f, at most b burning torches. 没有发生上述错误,所有加入和退出的调用均满足 ta≤f⋅pat_a\leq f\cdot p_a(受到浮点数计算误差的影响),且每一幕结束时至多有 bb 个火炬保持点燃。

作为对比,实际评测时使用的交互库只会将你的程序判定为 Not correct(无论发生了何种上述错误),Security violation!,Partially correct 或 Correct。此外,交互库自适应。也就是说,每一幕加入或离开的表演者数量可能取决于你的程序之前和当前的行为。样例交互库和标准交互库都会在你的程序发生上述错误时立刻终止程序。

交互样例

prepare()

join(3)

leave(2)

join(2)

join(3)
-


3, {2, 4}

0, {2}

3, {2, 4}

3, {2, 4, 7}

提示

样例解释

考虑 Q=4Q = 4,以上是评测器与程序之间的函数调用和返回值。

  • prepare():你可以在这个函数被调用时做一些预处理。
  • 表演开始,只有一个表演者 11,手持点燃的火炬。
  • join(3):三个表演者加入。返回 t1=3t_1 = 3,表演者 11 将表演者 2,3,42, 3, 4 的火炬点燃。返回编号列表 {2,4}\{2, 4\},表演者 1,31, 3 将自己的火炬熄灭。
  • leave(2):最右侧的两个表演者离开。返回 t2=0t_2 = 0,没有新的火炬被点燃。返回编号列表 {2}\{2\},表演者 22 的火炬保持点燃。
  • join(2):两个表演者加入。返回 t3=3t_3 = 3,表演者 22 将表演者 3,43, 4 的火炬点燃。返回编号列表 {2,4}\{2, 4\},表演者 33 将自己的火炬熄灭。
  • join(3):三个表演者加入。返回 t4=3t_4 = 3,表演者 22 将表演者 3,4,53,4,5 的火炬点燃,表演者 44 将表演者 5,6,75, 6, 7 的火炬点燃。返回编号列表 {2,4,7}\{2, 4, 7\},表演者 3,5,63, 5, 6 将自己的火炬熄灭。

初始时和四幕结束后的火炬状态

数据范围与评分标准

设 NN 表示任意时刻同时在台上的表演者数量的最大值。

  • Subtask 1(5 分):只有一次 leave 函数的调用。
  • Subtask 2(5 分):N≤700N\leq 700。
  • Subtask 3(10 分):N≤5000N\leq 5000。
  • Subtask 4(5 分):N≤2.5×104N\leq 2.5\times 10 ^ 4。
  • Subtask 5(10 分):N≤105N\leq 10 ^ 5。
  • Subtask 6(5 分):N≤5×105N\leq 5\times 10 ^ 5。
  • Subtask 7(60 分):无特殊限制。

部分评分:在 Subtask 7 当中,你的实际得分取决于每一幕的 tapa\frac {t_a} {p_a} 的最大值 PP。如果你希望得到满分,那么必须满足 ta≤pat_a \leq p_a 的限制。

  • 若 0≤P≤10\leq P\leq 1,得 6060 分。
  • 若 1<P≤21 < P\leq 2,得 3535 分。
  • 若 2<P≤32 < P \leq 3,得 2020 分。
  • 若 3<P≤53 < P\leq 5,得 1010 分。

对于所有数据,1≤N≤10171\leq N\leq 10 ^ {17},1≤Q≤5×1041\leq Q\leq 5\times 10 ^ 4。

限制

时间:1s。 空间:512MB。

原题面 PDF

Hydro 提交说明

只包含 light.h,实现三个函数,不写 main。平台私有头文件负责二进制通信,独立评测器保留自适应策略;隐藏输入中附加的子任务编号只用于恢复原评分,不会发送给选手。公开头文件与 sample_grader.cpp 用于普通样例本地联编。七档仍按原题5、5、10、5、10、5、60分计分,只有最后一档按比值分级。