정렬

• 주어진 연산은 같은 크기의 로테이션을 두번 돌리는 것과 동일하다. 한번의 로테이션 연산은 그 크기에 따라서 순열의 패리티가 바뀔수 있지만, 그것을 두번 반복하면 순열의 패리티는 보존된다. 따라서 주어진 순열이 홀순열이면 정렬 불가.
• 묶은 숫자를 한칸 앞으로 끼워넣으면, 이것은 인접한 3개 원소를 로테이트하는 것과 동일한 효과가 된다. 이것만으로도 순열의 패리티가 같은 한 어느 순열로도 변환이 가능하므로, 주어진 순열이 짝순열이면 정렬 가능.
  • 빵 정렬 참고
• 순열의 패리티만 확인하면 되므로 시간복잡도는 O(n)

"""Solution code for "BOJ 9078. 정렬".

- Problem link: https://www.acmicpc.net/problem/9078
- Solution link: http://www.teferi.net/ps/problems/boj/9078

Tags: [parity of permutation]
"""

from teflib import permcycle
from teflib import psutils


@psutils.run_n_times
def main():
    _N = int(input())
    nums = [int(x) - 1 for x in input().split()]
    print('YES' if permcycle.sign_of_permutation(nums) == 1 else 'NO')


if __name__ == '__main__':
    main()

• Dependency: teflib.permcycle.sign_of_permutation