Background

Day 1 Problem D.

The statement is translated from EGOI2024 gardendecoration. The translation comes from ChatGPT and has been manually proofread. If there are any mistakes, please contact rui_er.

7s 1GB.

This is a communication problem, and your program will be executed multiple times.

Problem Description

Every day on the way to and from school, Detje walks along a street with $N$ houses, numbered from $0$ to $N - 1$. Currently, resident $i$ lives in house $i$. To change things up, the residents decide to swap houses. The person who will move into house $i$ is the person who currently lives in house $a_i$.

In the garden of each house, there is a bird statue. These statues have two states: their wings are either open (as if flying) or closed (as if standing on the ground). The residents have strong preferences about how their bird statues should look. Currently, the bird statue in front of house $i$ is in the state that resident $i$ likes. The residents refuse to move into a house whose statue is not set to their preferred state. Detje wants to help them by adjusting the statues’ states so that they can move.

To do this, she does the following: each time she walks along the street (either to school or back home), she observes the birds one by one and may adjust some statues (by opening or closing their wings). Since she is very busy at both school and home, she does not remember the states of birds she has seen before. Luckily, she wrote down the list $a_0,a_1,\cdots,a_{N-1}$, so she knows which resident will move where.

Help Detje design a strategy that tells her which bird statues to adjust, so that the statues end up in the states the residents like. She may walk along the street at most 60 times, but to get a higher score, she should use as few walks as possible.

---

Interaction

This is a communication problem, and your program will be executed multiple times.

In each run, you should first read one line containing two integers $w$ and $N$, which are the walk index and the number of houses. In the first run, $w = 0$, in the second run, $w = 1$, and so on (explained in detail below).

In the second line of the input, there are $N$ integers $a_0,a_1,\cdots,a_{N-1}$, meaning that the person who will move into house $i$ currently lives in house $a_i$. The values $a_i$ form a permutation, i.e., every number from $0$ to $N - 1$ appears exactly once in the list $a_i$. Note that residents may choose not to move, so $a_i = i$ is allowed.

The residents will swap houses only once. This means that for a fixed test case, the value of $N$ and the list $a_i$ are the same in all runs of your program.

First run.

In the first execution of your program, $w = 0$. In this run, you should output an integer $W$ ($0 \le W \le 60$), which is the number of times Detje wants to walk along the street. Then your program should terminate. After that, your program will be executed another $W$ times.

Subsequent runs.

In the next run, $w = 1$; in the next one, $w = 2$; and so on, until the last run where $w = W$.

After reading $w, N$ and $a_0,a_1,\cdots,a_{N-1}$, Detje starts walking along the street.

• If $w$ is odd, Detje walks from home to school, passing the houses in the order $0, 1,\cdots, N - 1$.

  Your program should now read a line containing $b_0$, the current state of the statue in front of house $0$, where $0$ means closed and $1$ means open. After reading $b_0$, you should output one line containing the new state you want to set $b_0$ to, either $0$ or $1$.

  Then your program should read a line containing $b_1$, the state of the statue in front of house $1$, and output the new state for $b_1$. This continues for all $N$ houses. After Detje passes the last house (i.e., after reading and writing $b_{N-1}$), your program should terminate.

  Note: your program can only read the next value $b_{i+1}$ after writing the new value for $b_i$.

• If $w$ is even, Detje walks from school to home, passing the houses in the order $N - 1, N - 2,\cdots, 0$. That is, you start by reading and writing $b_{N-1}$, then $b_{N-2}$, and so on until $b_0$.

When $w = 1$, the input values $b_0,b_1,\cdots,b_{N-1}$ are the initial states of the bird statues (and also the residents’ preferred states). When $w > 1$, the input values $b_0,b_1,\cdots,b_{N-1}$ are the states that were set in the previous run of your program.

Finally, after the last run of the program, for all $i$, the value $b_i$ must be equal to the initial value $b_{a_i}$, otherwise the program will be judged as WA.

More details.

If the total running time of the $W + 1$ separate program executions exceeds the time limit, the program will be judged as TLE.

After outputting each line, be sure to flush standard output, otherwise your program may be judged as TLE. In Python, calling input() to read a line will automatically flush. In C++, cout << endl; flushes in addition to printing a newline; if you use printf, use fflush(stdout).

Input Format

See the Interaction section.

Output Format

See the Interaction section.

0 6
1 2 0 4 3 5

2

1 6
1 2 0 4 3 5
1

1

0

0

1

0

0

1

0

1

1

1

2 6
1 2 0 4 3 5
1

1

1

0

1

0

0

0

1

1

0

1

Hint

Sample explanation

The three samples in the statement correspond to three interactive processes for the same test case.

In the sample, we are given the following permutation of people among houses:

In the first run of the sample program ($w = 0$), it outputs $W = 2$, meaning that Detje will walk along the street twice (and the program will run two more times). Before the first walk, the birds in the gardens look as follows:

Then the program runs with $w = 1$, meaning Detje’s first walk. She passes the birds one by one from the left and may change their states. Before seeing bird $(i + 1)$, the sample program must output the state of bird $i$.

After Detje reaches school, the birds look as follows:

In the last run of the program ($w = 2$), Detje walks back home from school. Remember that in this case, she passes the birds from right to left and processes them in this order. This means she needs to decide the state of bird $i$ before seeing bird $(i - 1)$.

After she finishes the walk, the birds now look as follows:

Indeed, this is the correct configuration. For example, bird statue $3$ (the fourth from the left) is open (now $b_3 = 1$), which is correct because person $4$ will move there ($a_3 = 4$), and they originally had an open bird statue (originally $b_4 = 1$).

---

Constraints

For all testdata, $2\le N\le 500$, and you may use at most $W\le 60$ rounds.

• Subtask 1 (up to $10$ points): $N=2$.
• Subtask 2 (up to $24$ points): $N\le 15$.
• Subtask 3 (up to $9$ points): $a_i=N-1-i$.
• Subtask 4 (up to $13$ points): $a_i=(i+1)\bmod N$.
• Subtask 5 (up to $13$ points): $a_i=(i-1)\bmod N$.
• Subtask 6 (up to $31$ points): no special constraints.

---

Scoring

For each subtask that your program solves correctly, you will receive a score according to the following formula:

$$\textrm{score}=S_g\cdot\left(1-\frac{1}{2}\log_{10}(\max(W_g,3)/3)\right)$$

Here, $S_g$ is the full score for that subtask, and $W_g$ is the maximum number of rounds used by your program among all test cases in that subtask. Your score for each subtask will be rounded to the nearest integer.

Below is a graph of the score as a function of $W_g$. To get full score, you need to solve each test case in at most $3$ rounds.

Translated by ChatGPT 5