公式解説 では「\(A\) の中で値 \(i\) がある位置を表す配列 \(\text{pos}\)」を作成することで計算量が \(O(N^2)\) になることを回避していましたが、このような配列を作らない方法を解説します。この方針の方がほんの少し実装が楽かもしれません。

以下の手続きで正当な解を得ることができます。

• \(i=1,2,...,N\) の順に、以下の手続きを行う。
  • \(A_i\ne i\) である間、\(A_i\) と \(A_{A_i}\) をswapする。

一回のswapごとに \(A_i\) は正しい位置に移動するので、\(A\) のうちちょうど \(N-1\) 要素が正しい位置に存在することがないことも踏まえると、高々 \(N-1\) 回の操作で目標を達成できることが示せます。

計算量は、一回のswapに定数時間かかっているため、必ず \(N-1\) 回以下の swap で終了することも踏まえると \(O(N)\) です。これは十分高速です。

実装例(PyPy3)

N=int(input())
A=list(map(int,input().split()))
ans=[]
for i in range(N):
    A[i]-=1
for i in range(N):
    while A[i]!=i:
        ans.append((i+1,A[i]+1))
        pre=A[A[i]]
        A[A[i]]=A[i]
        A[i]=pre
print(len(ans))
for i in ans:
    print(*i)