시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 226 | 82 | 67 | 37.017% |
SUAPC의 성공에 힘입어, 연두는 “신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회”의 개최를 기획하고 있다. 이 대회는 신촌의 초등학교/중학교/고등학교에 다니는 $8$세 ~ $19$세의 학생이라면 누구든 참가할 수 있다.
연두는 컴퓨터 과학을 기반으로 연구한 자신만의 풍수지리설과 사주팔자를 굉장히 맹신한다. 따라서 이번 대회가 성공적으로 개최되기 위해서는, 참가자들의 나이에 따른 자리 배치가 매우 중요하다고 믿는다. 연두가 음양비트론에 의거하여 만든 데이터들에는, $x$번째 자리와 $y$번째 자리에 앉은 참가자의 나이를 bitwise AND 또는 bitwise OR 했을 때 어떤 값이 나와야 하는지 적혀있다.
그런데 SUAPC 2021 Winter에 이어 이 대회에도 후원사로 참여한 카카오에서, 몇 개의 자리를 골라 각 자리마다 특정 나이의 참가자를 앉혀달라는 부탁을 해왔다. 후원사의 부탁을 거절하고 싶지는 않은지라, 연두는 나머지 빈자리에 적절한 나이의 참가자를 잘 배치하여 자신의 모든 데이터를 만족시킬 수 있을지 궁금해졌다. 연두는 이미 $8$세 이상 $19$세 이하의 많은 학생을 확보해놓았다. 대회 준비에 바쁜 연두를 대신하여 연두가 원하는 대로 자리를 배치해주자.
다음과 같이 입력이 주어진다.
$N$
$a_1\ a_2\,\dots\ a_N$
$M$
$t_1\ x_1\ y_1\ z_1$
$\dots$
$t_M\ x_M\ y_M\ z_M$
빈자리에 $8$세 이상 $19$세 이하의 참가자를 배치하여 연두의 모든 데이터를 만족시킬 수 있다면, 첫 번째 줄에 $1$을 출력한다. 그다음 줄에, $1$번째, $2$번째, $\dots$, $N$번째 자리에 앉을 참가자의 나이를 공백으로 구분하여 출력한다. 그런 배치가 여러 가지면 그 중 아무거나 하나를 출력한다.
만약 그런 배치가 존재하지 않는다면, 대신에 첫 번째 줄에 $0$을 출력한다.
&
또는 $t_i = $ |
&
면, $x_i$번째 자리에 앉은 참가자의 나이와 $y_i$번째 자리에 앉은 참가자의 나이의 bitwise AND가 $z_i$여야 한다.|
면, $x_i$번째 자리에 앉은 참가자의 나이와 $y_i$번째 자리에 앉은 참가자의 나이의 bitwise OR이 $z_i$여야 한다.4 15 0 0 0 3 & 1 2 1 & 1 3 12 | 3 4 31
1 15 17 12 19
첫 번째 자리에는 $15$세의 참가자가 이미 배치되어 있다. 두 번째, 세 번째, 네 번째 자리에 각각 $17$세, $12$세, $19$세의 참가자를 배치하면, $15 \operatorname{\&} 17 = 1$, $15 \operatorname{\&} 12 = 12$, $12 \operatorname{|} 19 = 31$ 이므로 모든 데이터를 만족한다. 이 예제에서는 이 배치 이외에 가능한 다른 배치는 존재하지 않는다.
3 0 0 0 3 | 1 2 24 | 2 3 24 | 3 1 24
0
University > 신촌지역 대학생 프로그래밍 대회 동아리 연합 > 2021 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter) G번