P9729 [CEOI 2023] Light (Interactive Library Wanted).

Translated from CEOI 2023 Day 1 T1 [Light](https://www.ceoi2023.de/wp-content/uploads/2023/09/1-light.pdf).

At this year’s CEOI opening ceremony, there was a wonderful torch show. The performers stand in a line and are numbered from left to right starting from $1$. Each performer holds a torch, and initially exactly one performer holds a lit torch. The show consists of $Q$ acts. Before act $a$ begins, either $p_a > 0$ performers join from the right, and their torches are unlit; or the rightmost $p_a > 0$ performers decide to leave and extinguish their torches (if their torches are lit). The committee cannot control performers joining or leaving. The leftmost performer always stays on the stage. Once act $a$ is ready, the committee must announce a non-negative integer $t_a \geq 0$. For each performer holding a lit torch, they use it to light the torches of the $t_a$ people to their right. In other words, after the lighting step, performer $i$’s torch is lit if and only if at least one torch among performers $\max(1, i - t_a), \cdots, i$ was lit before the lighting step. $t_a$ should not exceed $5p_a$, and the smaller it is, the better. At the end of act $a$, the committee must tell each performer holding a lit torch whether to extinguish it. For aesthetic reasons, the rightmost performer should keep their torch lit. Also, to save fuel, the number of lit torches should not exceed $150$. Write a program to help the committee run the show under the constraints above. ### Interactive Format You need to implement the following three functions: ```c++ void prepare(); ``` Called at the very beginning of the program. You may do some preprocessing in this function, or do nothing. ```cpp pair join(long long p); ``` Called when $p_a > 0$ performers join. You need to return $t_a$ and the indices of all performers whose torches remain lit after this act ends. The list of indices must be in increasing order. Use `pair` to combine these two pieces of information. ```cpp pair leave(long long p); ``` Called when the rightmost $p_a > 0$ performers leave. You need to return $t_a$ and the indices of all performers whose torches remain lit after this act ends. The list of indices must be in increasing order. Use `pair` to combine these two pieces of information. If any return value violates the constraints, your program will be terminated immediately and judged incorrect. You must not read any information from standard input, and you must not write any information to standard output. However, you may freely write to standard error. You can link your program with the attached `sample_grader.cpp` for local testing. A detailed description of the sample interactive library is given below. ### Interactive Library The sample interactive library first reads an integer $Q$ from standard input. It writes to standard output information about the execution of the three functions above. First, the sample interactive library calls `prepare()`. Then it simulates $Q$ acts. In act $a$, the library reads an integer $p > 0$ or $q < 0$. If it reads $p > 0$, it means $p$ performers join the show, and it calls `join(p)`. If it reads $q < 0$, it means the rightmost $-q$ performers leave the show, and it calls `leave(-q)`. After terminating the program, the library will write one of the following messages to the standard output: - `Invalid input.` The input from standard input does not follow the format above. - `The stage is empty.` Fewer than one performer remains on the stage. - `Invalid return value.` The returned $t_a$ does not satisfy $0\leq t_a\leq 5p_a$, the list of performers whose torches remain lit is not sorted in increasing order, or the list contains an index smaller than $1$ or larger than the total number of performers still on the stage. - `Too many burning torches.` More than $150$ torches remain lit after some act ends. - `Rightmost torch not on fire.` The rightmost performer’s torch is not lit. - `Not all announced torches have been lit.` A torch that your program requested to remain lit had not been lit before. - `Correct: ratio at most f, at most b burning torches.` None of the errors above occurred, all `join` and `leave` calls satisfied $t_a\leq f\cdot p_a$ (affected by floating point errors), and at most $b$ torches remained lit at the end of each act. In contrast, the interactive library used in the actual evaluation will only judge your program as `Not correct` (no matter which of the errors above occurred), `Security violation!`, `Partially correct`, or `Correct`. Also, **the interactive library is adaptive**. That is, in each act, the number of performers joining or leaving may depend on your program’s previous and current behavior. Both the sample interactive library and the official interactive library will terminate the program immediately if your program makes any of the errors above.

N/A

N/A

#### Sample Explanation Consider $Q = 4$. Sample #1 is one possible interaction between the interactive library and your program. The input is the actual sequence of function calls, and the output is the actual return values of your program. - `prepare()`: You may do some preprocessing when this function is called. - The show starts with only performer $1$, holding a lit torch. - `join(3)`: Three performers join. Return $t_1 = 3$; performer $1$ lights the torches of performers $2, 3, 4$. Return the index list $\{2, 4\}$; performers $1, 3$ extinguish their own torches. - `leave(2)`: The rightmost two performers leave. Return $t_2 = 0$; no new torches are lit. Return the index list $\{2\}$; performer $2$ keeps their torch lit. - `join(2)`: Two performers join. Return $t_3 = 3$; performer $2$ lights the torches of performers $3, 4$. Return the index list $\{2, 4\}$; performer $3$ extinguishes their own torch. - `join(3)`: Three performers join. Return $t_4 = 3$; performer $2$ lights the torches of performers $3, 5$, and performer $4$ lights the torches of performers $5, 6, 7$. Return the index list $\{2, 4, 7\}$; performers $3, 5, 6$ extinguish their own torches. #### Constraints and Scoring Let $N$ be the maximum number of performers that are on the stage at the same time at any moment. - Subtask 1 (5 points): There is only one call to the `leave` function. - Subtask 2 (5 points): $N\leq 700$. - Subtask 3 (10 points): $N\leq 5000$. - Subtask 4 (5 points): $N\leq 2.5\times 10 ^ 4$. - Subtask 5 (10 points): $N\leq 10 ^ 5$. - Subtask 6 (5 points): $N\leq 5\times 10 ^ 5$. - Subtask 7 (60 points): No special constraints. **Partial scoring**: In Subtask 7, your actual score depends on the maximum value $P$ of $\frac {t_a} {p_a}$ over all acts. If you want to get full score, you must satisfy the constraint $t_a \leq p_a$. - If $0\leq P\leq 1$, you get $60$ points. - If $1 < P\leq 2$, you get $35$ points. - If $2 < P \leq 3$, you get $20$ points. - If $3 < P\leq 5$, you get $10$ points. For all testdata, $1\leq N\leq 10 ^ {17}$ and $1\leq Q\leq 5\times 10 ^ 4$. #### Limits Time: 1 s. Memory: 512 MB. Translated by ChatGPT 5