P17274 [eJOI 2026] Elevator

*This is a communication problem.* There is a building with floors numbered from $0$ to $N$. Floor $0$ is the ground floor, and above floor $N$ is the rooftop. Thus, including the rooftop, the building has $N+2$ levels. Each floor $f$ with $0\le f\le N$ is occupied by exactly one resident and has a secret integer $v_f$ with $0\le v_f\le 3$, known only to that resident. Karlsson lives on the rooftop. His objective is to determine as many values among $v_0,v_1,\ldots,v_N$ as possible, while every resident cooperates to maximize the number of values he can recover. The residents communicate using the building's elevator as follows. The elevator starts on floor $0$ and travels only upward. It has buttons labelled $1$ through $N$. Initially no buttons are pressed; once pressed, a button remains pressed permanently. The elevator stops and opens on floor $f$ if either $f=0$ or the button for floor $f$ was pressed at an earlier stop. After visiting the highest floor whose button has been pressed, or floor $0$ if no button is ever pressed, the elevator goes directly to the rooftop without stopping at any remaining floors. When the elevator stops on floor $f$: 1. The resident sees the complete set of buttons currently pressed. 2. Based only on this information and on $v_f$, the resident may press any subset of the currently unpressed buttons for floors strictly above $f$. 3. The elevator moves to the lowest higher floor whose button is pressed, or to the rooftop if every floor with a pressed button has already been visited. If the elevator does not stop at a floor, that floor's resident cannot press any buttons. At the rooftop, Karlsson sees only the final set of pressed buttons. From this information, he tries to recover as many of $v_0,v_1,\ldots,v_N$ as possible. The values of $v$ are fixed before your program starts and do not change during the process. ### Implementation details There are $T$ test cases. Submit one file implementing the following two functions. ```cpp std::vector press_buttons(int subtask, int N, int f, int v, std::vector p) ``` - `subtask`: the subtask number, where $0\le\texttt{subtask}\le 4$; - $N$: the number of the last floor; - $f$: the current floor, where $0\le f\le N$; - $v$: the value $v_f$ on floor $f$; - $p$: the currently pressed buttons, in increasing order. This function is called when the elevator opens on floor $f$, which happens when $f=0$ or the button for $f$ was pressed at an earlier stop. It is not called for a floor at which the elevator does not stop. The return value is the list of new buttons to press. Their order is irrelevant. Every returned button $x$ must satisfy: - $f

The sample grader makes all function calls for all test cases in one execution. Input format: - line $1$: $T$, $N$, and the subtask number $S$; - line $1+i$: $N+1$ integers $v_0,v_1,\ldots,v_N$ for test case $i$.

Output format: - line $i$: the number of correctly recovered values in test case $i$; - line $T+1$: the final score. For detailed feedback, change the macro `DETAILED` from `false` to `true` on the first line of the grader. To let the grader generate values of $v_f$, change `AUTO_GENERATE` from `false` to `true` on its second line.

### Example The example has one test case with the following floor values: ```text 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 ``` An example interaction is: | Participant program | Jury program | |---|---| | | `press_buttons(0, 60, 0, 1, {})` | | `return {2}` | | | | `press_buttons(0, 60, 2, 0, {2})` | | `return {13, 42}` | | | | `press_buttons(0, 60, 13, 0, {2, 13, 42})` | | `return {}` | | | | `press_buttons(0, 60, 42, 1, {2, 13, 42})` | | `return {}` | | | | `answer(0, 60, {2, 13, 42})` | | `return {1, -1, 0, -1, -1, ..., -1}` | | This interaction correctly recovers values $0$ and $2$. Every other returned value is $-1$ because Karlsson did not recover it. ### Constraints - $N=60$ - $T\le 10\,000$ - $0\le v_i\le 3$ for every $0\le i\le N$ ### Subtasks | Subtask | Points | Additional constraints | Floors to recover for full points | |:--:|:--:|---|:--:| | 0 | 0 | The example. | - | | 1 | 15 | $0\le v_i\le 1$; $v_0=v_N=1$; if $v_i=0$, then $v_{i+1}=1$ for every $0\le i