테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 정렬 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:permcycle#sign_of_permutation|teflib.permcycle.sign_of_permutation]]

{{tag>BOJ ps:problems:boj:골드_2}}