【Atcoder】ABC 350 C問題

コンテスト名

AtCoder Beginner Contest 350

考えたこと

整数の組 (i,j) をswapしてsortする
↓
選択ソート？

結果
計算量$O(n^2)$なので当然TLE

次に考えたこと

ヒープソートを使う

結果
heapqを使えばsortだけならいけそうだが、問題文に
$「l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。」$
と書いてあるので（自分には）不可能。

公式解説

https://atcoder.jp/contests/abc350/editorial/9810?lang=ja
https://atcoder.jp/contests/abc350/editorial/9832

考察

なるほど。そもそも最小値を見つける必要がなく、必ずi番目の数字はiになる訳か。（当たり前）
ただ、$「現在 A の中で i がどこにあるか」$を探す際にindexメゾットを使うと
$O(n^2)$になってしまうから「A の中で値 i がある位置を表す配列」を用意する必要があるわけね。

ということで公式解説の間違い例
https://atcoder.jp/contests/abc350/editorial/9832
を使って書き換えました。

n=int(input())
a=list(map(int,input().split()))
answer=[]

pos=[0]*(n+1)
for i in range(n):
    pos[a[i]]=i
for i in range(n):
    if a[i]!=i+1:
        idx=pos[i+1]
        a[i],a[idx] = a[idx],a[i]
        pos[a[i]],pos[a[idx]]= pos[a[idx]],pos[a[i]]
        answer.append((i+1,idx+1))

print(len(answer))
for a in answer:
    print(*a)