스왑 스왑

• 두번의 스왑이므로, 순열의 패리티가 보존된다. 따라서 주어진 순열이 홀순열이라면 정렬이 불가능하다.
• 짝순열인 경우 정렬이 가능하다는 것은, i와 j를 같은 값으로 두면 주어진 연산이 인접 3개 원소를 로테이션하는것과 동일해진다는 것을 통해서 알수 있다. 인접 3개 원소를 로테이션 하는 연산으로 원하는 순열로 변환이 가능하다는 것은 빵 정렬 과 동일
• 주어진 순열의 패리티만 확인하면 되므로 시간복잡도는 O(n)
  • 공식 풀이에서는 버블정렬을 통해 반전수를 O(n^2)에 구하는 방법으로 설명하고 있다. n이 작아서 통과하는데에는 문제 없다.

"""Solution code for "BOJ 34728. 스왑 스왑".

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

Tags: [parity of permutation]
"""

import sys
from teflib import permcycle


def main():
    _N = int(sys.stdin.readline())
    a = [int(x) - 1 for x in sys.stdin.readline().split()]
    print('Yes' if permcycle.sign_of_permutation(a) == 1 else 'No')


if __name__ == '__main__':
    main()

• Dependency: teflib.permcycle.sign_of_permutation