페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2491

[중등부] 2025 KOI 1차대회 대비 모의고사 (2주차)

비둘기
스페셜 저지
서브태스크
2초 1024MB

문제

전깃줄 위에 일렬로 N마리의 비둘기가 앉아 있다. 왼쪽에서부터 1, 2, 3, \dots , N번 비둘기이다. 각 비둘기는 오른쪽 또는 왼쪽을 바라보고 있다.

비둘기는 특정한 규칙에 따라 운다.

  • i번 비둘기가 왼쪽을 바라보고 있다면, 자신보다 왼쪽에 있으면서 오른쪽을 바라보는 비둘기의 수만큼 운다.

  • i번 비둘기가 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있으면서 왼쪽을 바라보는 비둘기의 수만큼 운다.

각 비둘기가 운 횟수가 주어졌을 때, 비둘기의 방향을 복원하라.


입력

첫째 줄에 비둘기의 수를 나타내는 정수N (1 \leq N \leq 10^6)이 주어진다.

둘째 줄에 각 비둘기가 운 횟수 A_1, A_2, \dots , A_N (0 \leq A_i \leq N)이 공백을 사이에 두고 주어진다.


출력

가능한 비둘기의 배치가 존재한다면, 길이 N의 0과 1로 이루어진 배열을 출력한다.

 i번째 수가 0이라면 왼쪽을, 1이라면 오른쪽을 바라보고 있음을 뜻한다.

가능한 배치가 여러 개라면 아무거나 출력한다. 불가능하다면 -1을 출력한다.


부분문제

번호 점수 조건
#120점

N \le 20

#220점

N\le 100

#320점

N\le 500

#420점

N\le 5000

#520점

추가 제약 조건 없음


예제 #1

5
3 1 1 1 2
1 0 0 1 0

예제 #2

3
1 2 2
-1

예제 #3

4
1 1 1 3
1 1 1 0

예제 #4

1
1
-1

예제 #5

20
8 8 2 2 6 6 4 5 5 6 4 7 3 3 9 2 2 11 1 1
-1

예제 #6

20
10 1 9 2 2 7 7 4 4 5 5 4 6 3 7 2 2 9 1 10
1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0
로그인해야 코드를 작성할 수 있어요.