题目描述

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.

std::vector<int> press_buttons(int subtask, int N,
                               int f, int v, std::vector<int> 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<x\le N$;
• $x$ is not already in $p$ and appears exactly once in the returned array.

std::vector<int> answer(int subtask, int N, std::vector<int> p)

• subtask: the subtask number, where $0\le\texttt{subtask}\le 4$;
• $N$: the number of the last floor;
• $p$: the final set of pressed buttons, in increasing order.

This function is called exactly once per test case when the elevator reaches the rooftop.

The returned array must have length $N+1$. Its $i$-th element must equal $v_i$ if Karlsson can recover that value, and $-1$ otherwise.

Important: The people in the building cannot communicate in any other way. Your program is run as $N+2$ separate processes: one for each floor and one for the rooftop. Each floor process receives at most $T$ calls to press_buttons; the rooftop process receives exactly $T$ calls to answer. Do not assume any shared state, including global variables. Every process has its own 64 MiB memory limit, and all calls, up to $(N+1)T$ calls to press_buttons and exactly $T$ calls to answer, must finish within 10 seconds.

输入格式

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:

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		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<N$	60
2	35	$0\le v_i\le 1$	40
3	15	$0\le v_i\le 2$	30
4	35	$0\le v_i\le 3$	25

Scoring

If your program returns an incorrectly recovered value or performs an invalid operation, such as returning a vector of the wrong length, in any test case of a subtask, it receives zero points for that subtask.

For one test case, the recovered count is the number of returned positions that are not $-1$. Let $K$ be the minimum recovered count over all test cases of a subtask. Each subtask contains one test with at most $10\,000$ test cases. Its score is:

Subtask	Range of $K$	Points
0	-	$0$
1	$K<60$	$0.25K$
	$K\ge 60$	$15$
2	$K<30$	$0.5K$
	$30\le K<40$	$2K-45$
	$K\ge 40$	$35$
3	$K<30$	$0.5K$
	$K\ge 30$	$15$
4	$K<20$	$0.7K$
	$20\le K<25$	$4K-66$
	$K\ge 25$	$35$