시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB (추가 메모리 없음)69627924843.739%

문제

영우는 나코더 신입생들을 환영하기 위해 정성스럽게 입부 환영 카드를 만들었다. 입부 환영 카드에서 소환된 기장 동현이의 환영이 신입생들을 환영할 것이다. 부기장인 이환이는 환영 카드의 색칠을 맡았다. 이환이는 각 카드를 일렬로 줄지어 놓고 빨간색, 초록색, 파란색 중 하나의 색으로 칠하려 한다. 그런데 그중 몇 개의 카드는 영우가 이미 색칠했다. 색칠은 다음 규칙에 따라야 한다.

  • 단조로움을 피하기 위해, 인접한 카드는 서로 다른 색으로 칠해야 한다.
  • 이미 색칠된 카드에 덧칠할 수 없다.
  • 카드의 순서를 바꿀 수 없다.

하지만 이환이는 서울과학고등학교 동아리 '싸이컴'의 상훈이와 테트리스 대결을 해야 하기 때문에 환영 카드를 색칠할 시간 따위는 없다. 그러니까 신입생 환영 카드의 색칠은 여러분이 직접 하도록 하자.

입력

첫째 줄에 카드의 개수를 나타내는 정수 N이 주어진다. 둘째 줄에 N 개의 정수가 공백으로 구분되어 주어진다. i 번째 정수 aii 번째 카드의 색깔을 나타낸다. 1, 2, 3은 각각 빨간색, 초록색, 파란색을 의미하며, 0은 i 번째 카드가 색칠되어 있지 않음을 의미한다.

출력

유일한 줄에 N 개의 정수를 공백으로 구분하여 출력한다. 각 정수는 1, 2, 3 중 하나여야 하며, 주어진 조건에 맞아야 한다. 가능한 방법이 여러 가지인 경우, 그중 아무거나 출력한다. 만약 모든 조건에 맞는 색칠이 불가능하다면, 유일한 줄에 –1만 출력한다.

제한

  • 1 ≤ ≤ 1,000,000
  • 0 ≤ a≤ 3
  • 주어지는 모든 수는 정수이다.

서브태스크 1 (29점)

 처음에 아무 카드도 색칠되어 있지 않다.

서브태스크 2 (25점)

 처음에 색칠되어 있는 카드는 모두 빨간색으로 색칠되어 있다.

서브태스크 3 (46점)

 추가 제한 조건이 없다.

예제 입력 1

5
1 0 2 0 3

예제 출력 1

1 3 2 1 3

유일하게 가능한 색칠이다.

예제 입력 2

6
0 0 0 0 0 0

예제 출력 2

1 2 1 2 1 2

가능한 색칠 중 하나이다.

예제 입력 3

2
1 1

예제 출력 3

-1

색칠이 불가능하다.

출처

High School > 경기과학고등학교 > 2022 IamCoder Qualification Test 1번

채점 및 기타 정보

  • 예제는 채점하지 않는다.