P6585 Neutron Decay

This is an **interactive problem**. Some prerequisite knowledge that may be useful: A proton carries one unit of positive charge. An electron carries one unit of negative charge. A neutron has no charge.

There are $n$ neutrons in front of Youyou and Xiao Z, arranged in a line from left to right. These neutrons are fixed by the strong force at positions numbered $1 \sim n$. Xiao Z has a weak-interaction decay machine Wadm (Weak Action Decay Machine). Each time, Wadm can cause one neutron to undergo weak decay, releasing an electron and a proton (neutrinos are ignored in this problem). Then, according to Youyou's or Xiao Z's instruction, Wadm keeps one of the two particles and removes the other from the system. In short, Wadm can turn one neutron into an electron or a proton. Now Xiao Z wants to play a game with Youyou: they take turns using Wadm to operate on one neutron, turning it into an electron or a proton. However, if an electron and a proton are adjacent, then due to the strong Coulomb attraction, they will break free from the strong-force constraint, so this situation is not allowed. If it is someone's turn and no position can be operated anymore, then that person loses. Youyou happily agrees to Xiao Z's request, but facing the clever Xiao Z, Youyou has to ask you for help. In particular, **if all neutrons eventually become the same kind of particle, then the second player wins**. If you help Youyou defeat Xiao Z, Youyou will give you a Wadm as a reward! ## Interaction Your program should read from standard input and write to standard output. The input contains two integers `n task_id`, representing $n$ in the statement and the subtask id. Then you need to output an integer `order`. $\text{order}$ can only be $0$ or $1$. $0$ means you choose to move first, and $1$ means you choose to move second. Next, you should interact with the interactive library through standard input/output according to whether you move first or second. - If it is your turn, you should output two integers `place type`, meaning you turn the neutron at position $\text{place}$ into an electron ($\text{type}=-1$) or a proton ($\text{type}=1$). You must ensure that: - $\text{place} \in [1,n]$ and that position is operable; - $\text{type} \in \{-1,1\}$; - **you have flushed the output buffer**. In C or C++, you may use `fflush(stdout)`. In C++, you may also use `cout

See “Interaction”.

See “Interaction”.

* Subtask 1 (5 points): $n \leq 4$. * Subtask 2 (8 points): $n \leq 8$. * Subtask 3 (12 points): $n$ is even, special strategy of the interactive library*. * Subtask 4 (15 points): special strategy of the interactive library*. * Subtask 5 (20 points): $n$ is even. * Subtask 6 (40 points): no special constraints. *Special strategy of the interactive library: each time it is the interactive library's turn, it finds the leftmost position that can be operated, and then if that position can be operated into a proton, it operates it into a proton; otherwise, it operates it into an electron. For all testdata, it is guaranteed that $1 \leq n \leq 2^{10}$. Translated by ChatGPT 5