[Codeforces] Codeforces Round #669 C. Chocolate Bunny

問題

方針

剰余の単調増加性を利用して解きます。自然数 \( x, y \) を用いて \( x \bmod y \) と \( y \bmod x \) を考えます。また、\( x \neq y \) とします。

\[ y \bmod x < x \bmod y \]

を満たすとき、\( x < y \) であることが分かります。つまり、\( x < y \) であるとき、

\[ x = x \bmod y\]

を満たします。したがって、”? i j” と “? j i”というクエリを投げた時、\( p_i \) または \( p_j \) のどちらかの値が判明します。

したがって、\( p_i \bmod p_j < p_j \bmod p_i \) を満たす \( i \) を更新し、全探索します。

コード