公式解説と同じようにサイクルを考えます。

まず、適当な順列 \(A\) を用いて質問します。

その後、\(i = 0, 2, \dots ,N - 2\) の順番で以下の操作をします。

• \(\mathrm{swap}(A_{i}, A_{i + 1})\) を行ったあと質問し、サイクルの数が減ったらそのままにし、増えたら \(\mathrm{swap}(A_{i}, A_{i + 1})\) を再度行い元に戻す

この操作後、全ての頂点が同じサイクル上にいます。

つまり答えを \(B\) としたとき、全ての \(i\) について\(A_{P_{i}} = B_{i}\) が成り立つような完全順列 \(P\) が存在します。

この \(P\) を求めることができたら答えが求まります。

この \(P\) の代わりに以下の条件を満たす順列 \(Q\) を求めます。

• \(Q_{0} = 0\)
• \(Q_{i + 1} = P_{Q_{i}}\)

このような \(Q\) と \(P\) は一対一対応します。

この \(Q\) は以下の性質が成り立ちます。

• \(1\leq i < j < N\) を満たす \(i,j\) を選び、\(A\) に対して、\(\mathrm{swap}(A_{0}, A_{Q_{i}}), \mathrm{swap}(A_{0}, A_{Q_{j}})\) をこの順に行うと、サイクルの数は \(1\) になる。

\(i, j\) を逆にすると以下のようになります。

• \(1\leq j < i < N\) を満たす \(i,j\) を選び、\(A\) に対して、\(\mathrm{swap}(A_{0}, A_{Q_{i}}), \mathrm{swap}(A_{0}, A_{Q_{j}})\) をこの順に行うと、サイクルの数は \(3\) になる。

よって、 \(2\) つの数 \(a, b\) が \(Q\) に出てくる順番を \(1\) 回の質問で知ることができます。

このことより、 \(Q\) はソートすることでわかるので、\(P\) もわかり、\(B\) もわかります。

ソートは \(O(N\log(N))\) 回でできるので、今回の制約では十分です。

ただし、最初に \(N\) 回の比較をしていることや \(\log_{2}(N)\) がほぼ \(9\) であることから、クエリ回数がギリギリであることに注意してください。

自分の実装では、std::sort を用いると WA になり、std::stable_sort を用いると AC となりました。

実装例