No.3783 Choose Disjoint Semicircles
タグ : / 解いたユーザー数 7
作問者 :
Problem Statement
You are given $Q$ queries. Each query gives an even number $N$ that is at least $6$ and a permutation $P=(P_0,P_1,\cdots,P_{N-1})$ of $\left(1,2,\cdots,N\right)$ (note that the indices start from $0$). Print 1 integer $i$ between $0$ and $N-1$, inclusive.
Using your submitted program, the judge plays the following game. A test case is judged AC if and only if this game succeeds.
First, the judge runs your program as $2$ independent processes. For convenience, we distinguish them by calling them process $1$ and process $2$. However, each process is not given any information on whether it is running as process $1$ or as process $2$. The judge first decides the number of queries $Q$ and inputs $Q$ to each of the $2$ processes. Then, the following operation is repeated $Q$ times. (See also the explanation in the sample below.)
- Decide an even number $N$ that is at least $6$, a permutation $P=(P_0,P_1,\cdots,P_{N-1})$ of $\left(1,2,\cdots,N\right)$, an integer $r$ between $0$ and $N-1$, inclusive, and an integer $p$ such that $p\in \{1,2\}$. Of these, $r$ and $p$ are not given to either process; they are private information held only by the judge.
- Input $N$ and $P$ to process $p$ and receive its output. Let $i$ be the received integer.
- Take the cyclic segment of length $\frac{N}{2}$ starting from $P_i$ and reverse that part. Then, let $X$ be the set of values targeted by this operation. More precisely, for the value of $P$ at this point, define the set of integers $X$ as $X=\{P_{(i+j) \bmod N}|0 \leq j < \frac{N}{2}\}$, and then, for each integer $j$ such that $0 \leq j < \frac{N}{2}$, simultaneously replace $P_{(i+j) \bmod N}$ with $P_{(i+\frac{N}{2}-1-j) \bmod N}$.
- Cyclically shift $P$ to the left $r$ times. (That is, for each integer $j$ such that $0 \leq j < N$, simultaneously replace $P_j$ with $P_{(j+r) \bmod N}$.)
- Input $N$ and $P$ to the process other than process $p$ (that is, process $3-p$) and receive its output. Let $i'$ be the received integer.
- For the value of $P$ at this point, define the set of integers $Y$ as $Y=\{P_{(i'+j) \bmod N}|0\le j < \frac{N}{2} \}$. The operation succeeds if the intersection of $X$ and $Y$ is empty, and fails otherwise.
The game succeeds if and only if all $Q$ operations succeed.
Constraints
- $1 \le Q \le 10000$
- $6 \le N \le 2 \times 10^5$
- $N$ is even
- $(P_0,P_1,\cdots ,P_{N-1})$ is a permutation of $(1,2,\cdots ,N)$
- The sum of $N$ over the $Q$ queries is at most $2 \times 10^5$
- All input values are integers
Input and Output
First, the number of queries $Q$ is given in the following format.
$Q$
Then, each query is given in the following format.
$N$
$P_0\ P_1\ \cdots\ P_{N-1}$
For each query, output in the following format.
$i$
Note that the next query is not input until both processes have finished processing $1$ query.
If your output does not satisfy the constraints or the operation in the problem statement fails, the next query is not given, and -1 is input instead. In this case, terminate your program immediately.
Notes
- After each output, append a newline and be sure to flush standard output.
- If you print invalid output or your program terminates midway, the judge result is undefined.
Sample
As an example, consider a case with $Q=1$. First, both processes are given the following input.
1
Suppose the judge decides $N=8,r=3,p=1,P=(4,1,6,8,2,3,7,5)$. Then, process $p=1$ is given the following input.
8
4 1 6 8 2 3 7 5
Suppose process $1$ outputs the following in response.
6
Then, $X=\{7,5,4,1\}$. Applying the segment reversal operation to $P$ gives $P=(5,7,6,8,2,3,1,4)$, and it is further cyclically shifted to the left $r=3$ times, so the process other than process $p$, that is, process $2$, is given the following input.
8
8 2 3 1 4 5 7 6
Suppose process $2$ outputs the following in response.
7
Then, $Y=\{6,8,2,3\}$. Since $X\cap Y= \emptyset$, this operation succeeds.
Since all $Q=1$ operations succeeded, this case is judged AC.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。