ARC 110 C - Exoswap

$1, \ldots, n$ を並び替えた数列を、隣同士の入れ替えを適当な順番でちょうど1回ずつ行ってもとに戻すことが可能か判定する。

C - Exoswap

解説

実装に合わせるため、与えられる数列は $0, \ldots, n - 1$ を並び替えたものとし、インデックスも $0$ はじまりで考える。例えば $(1,3,0,4,2)$ の場合、$0$ を右に動かす操作はできない。なぜなら、一度 $0$ を右に動かしてしまうと同じだけ左に動かす操作が必要だが、同じ入れ替えは一度しかできないからである。つまり、$0$ を $2$ 番目から $0$ 番目に動かす操作は最初に行ってよい。その後、$2$ を $4$ 番目から $2$ 番目に動かす操作を行う。可能な操作はこれだけで、これでもとに戻っていなければ不可能である。
具体的な手順は次のようになる。数列を前から順に見ていき、$0$ が見つかったとする。そのインデックスを $i$ とすると、$i$ 番目から $0$ 番目までを順に入れ替える。次に、$i$ が見つかったらとする。そのインデックスを $j$ とすると、$j$ 番目から $i$ 番目を順に入れ替える。以上の操作を数列の最後まで行い、最後に入れ替えがちょうど $n - 1 $ 回行われたかどうかと実際にその入れ替えによって数列がもとの順に戻ったかをチェックする。

実装

n = int(input())
(*lst,) = map(lambda x: int(x) - 1, input().split())
ans = []
cur = 0
for i in range(n):
    if lst[i] == cur:
        for j in range(cur, i)[::-1]:
            ans.append(j)
        cur = i
for i in ans:
    lst[i], lst[i + 1] = lst[i + 1], lst[i]
if len(ans) == n - 1 and lst == list(range(n)):
    print(*map(lambda x: x + 1, ans), sep="\n")
else:
    print(-1)

Submission #18604216 - AtCoder Regular Contest 110（Sponsored by KAJIMA CORPORATION）