빵 정렬

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

"""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()

• Dependency: teflib.permcycle.sign_of_permutation