시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB37161453.846%

문제

그림과 같이 생긴 추가 있다. 각 추는 그에 붙여진 번호와 같은 무게를 갖고 있으며, 1번부터 n번까지 번호가 붙은 추가 각각 한 개씩의 있다고 하자. 다음과 같은 규칙을 만족시키면서, 천칭저울에 추를 매달려고 한다.

  1. 임의의 추의 왼쪽에는 그 추보다 가벼운 추만 달 수 있고, 오른쪽에는 그 추보다 무거운 추만 달 수 있다.
  2. 천칭저울의 좌우에 달린 추의 모양은 기둥을 중심으로 대칭을 이루어야 한다. 추가 홀수개 주어지는 경우에는, 그 중 하나의 추를 쓰지 않는다.
  3. 깊이 d에 추를 매다는 조건은 깊이 d-1에 추들이 모두 차있을 경우뿐이다. 즉, 추의 깊이가 최소가 되도록 추를 배치한다.
  4. 동일한 깊이에 추를 매달 경우, 큰 저울을 중심으로 왼쪽 모양에서는 해당 깊이의 왼쪽부터 추를 매달고 큰 저울을 중심으로 오른쪽 모양에서는 해당 깊이의 오른쪽부터 추를 매단다.
  5. 추를 모두 매단 후에는, 천칭저울이 평형을 이루어야 한다. (천칭저울은 양쪽에 매달린 추들의 무게 합이 서로 같을 경우에 평형을 이룬다고 하자.)

입력

첫 줄에 n이 주어진다. (2 ≤ N ≤ 100,000)

출력

첫째 줄에 천칭저울 왼쪽의 추들을 출력하고, 둘째 줄에 천칭저울 오른쪽의 추들을 출력한다. 양쪽 추들이 이루는 모양을 루트가 있는 트리로 생각하고, 각 트리를 프리오더 (pre-order)로 운행한 결과를 출력하면 된다. 불가능한 경우에는 첫째 줄에 -1을 출력한다.

예제 입력 1

9

예제 출력 1

8 2 1 9
4 3 6 7

힌트

출처

  • 문제를 번역한 사람: author5