問題一覧 > 通常問題

No.3783 Choose Disjoint Semicircles

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / コミュニケーション問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : askr58 / テスター : 👑 AngrySadEight / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 13699 / 自分の提出
問題文最終更新日: 2026-10-30 21:07:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 520 (順位表) の他の問題:

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.)

  1. 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.
  2. Input $N$ and $P$ to process $p$ and receive its output. Let $i$ be the received integer.
  3. 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}$.
  4. 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}$.)
  5. 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.
  6. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。