Yukicoder No.326 あみだますたー

練習会でやった。周りがみな苦戦していた。

solution

バブルソートぽくやる。

$L \le 6000$の制約には抵触しない。 高々$99 + 98 + \dots + 1 = 4950$回のswapで済む。

implementation

あみだの状態の持ち方に注意する必要がある。 あみだの状態は$N = { 0, 1, \dots, N-1 }$として全単射$f : N \to N$と見ることができる。 配列で持つとして、写像f[x] = yのような持ち方と逆写像f[y] = xのような持ち方が共に自然であり、どちらを使ってもよいが、混同するとバグになる。

#!/usr/bin/env python3
n = int(input())
f = list(range(1,n+1))
for _ in range(int(input())):
    x, y = map(int,input().split())
    x -= 1
    y -= 1
    f[x], f[y] = f[y], f[x]
sigma = list(map(int,input().split()))
for i in range(n):
    f[i] = sigma[f[i] - 1] - 1
ans = []
for i in range(n):
    for j in range(n-1):
        if f[j] > f[j+1]:
            f[j], f[j+1] = f[j+1], f[j]
            ans += [(j, j+1)]
print(len(ans))
for x, y in ans:
    print(x+1, y+1)