테페리넷

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

====== 빵 정렬 ======

===== 풀이 =====
  * 인접한 3개 원소를 로테이트 시키는 연산으로는, 순열 패리티가 같은 한, 어떤 순열로도 변환이 가능하다.
    * [[ps:tutorial:정렬#모든 원소의 값이 다른 경우|스왑 기반 정렬]] 참고
  * 결국 현재 순서와, 목표 순서의 순열 패리티가 같은지만 확인해보면 된다. 순열 사이클 분할을 이용해서 O(n)에 구할수 있다. 
    * 세그트리 등을 사용해서 반전수를 직접 계산할 필요는 없다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 5000. 빵 정렬".

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

from teflib import permcycle


def main():
    _n = int(input())
    cur_order = [int(x) - 1 for x in input().split()]
    target_order = [int(x) - 1 for x in input().split()]

    cur_parity = permcycle.sign_of_permutation(cur_order)
    target_parity = permcycle.sign_of_permutation(target_order)
    print('Possible' if cur_parity == target_parity else 'Impossible')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:permcycle#sign_of_permutation|teflib.permcycle.sign_of_permutation]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}