ARC110 C - Exoswap (500)
小さい数から前に持って行くことにする
既に移動済みの数なら飛ばす
一つずつ前にswapする
最初のswap以外で$ p_i != iの場合、その数を移動させる必要があるが既にそこの移動を使っているので構築不可能
移動を記録していってその回数が$ N-1回で無かったり、最終的にソートされていなかったりいたら構築不可能
swap回数は$ O(N)、既に移動済みかどうかの確認が全体で$ O(N \log N)なので全体で$ O(N \log N)
問題: https://atcoder.jp/contests/arc110/tasks/arc110_c
提出: https://atcoder.jp/contests/arc110/submissions/18586126
#ARC110 #鹿島建設プログラミングコンテスト2020 #500pt #C #ARC #AtCoder
#O(NlogN)