31676번 - 특별한 케이크 (hard) 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 146 | 54 | 44 | 42.718% |
문제
흐에에...
어둠을 틈타 누군가가 시이(swi)의 엄청난 케이크를 또 먹어버렸다!
여느날처럼 케이크를 좋아하는 시이는 근처 가게에서 사온 엄청난 케이크를 식탁 위에 올려놓고 감상하고 있었다. 하지만 기숙사 히터가 너무 따뜻했던 탓에 시이는 잠들고 말았고, 시이가 잠든 사이 케이크가 사라져버렸다!
케이크를 먹은 사람은 사건 당시 기숙사에 있던 시이와 시이를 제외한 $N$명의 사람 중 한 명이다. 시이는 범인을 찾기 위해 자신이 자던 동안 기숙사에 있던 $N$명의 학생을 동시에 추궁했다. 시이는 각 학생이 한 진술을 다음 두 종류의 유형 중 한 가지로 정리했다.
- 명단 $S$에 있는 학생 가운데 범인이 있다.
- 명단 $S$에 있는 학생 가운데 범인이 없다.
만약 $N$명의 학생 중 한 명이 범인이라면 나머지 학생은 모두 범인을 알 것이므로 범인을 제외한 모든 학생은 사실대로 진술할 것이고, 범인은 자신이 케이크를 먹은 사실을 숨기기 위해 거짓으로 진술할 것이다. 그러나 $N$명의 학생 모두가 범인이 아니라면 시이가 케이크를 먹어버린 것이기 때문에 모든 진술의 진위를 알 수 없다.
시이는 $N$개의 진술을 바탕으로 범인일 가능성이 있는 학생을 추려내고자 한다. 어떤 학생이 범인이라 가정했을 때 $N$개의 진술에 모순이 없다면 그 학생을 범인일 가능성이 있는 학생이라고 한다. 만약 $N$명의 학생 가운데 범인일 가능성이 있는 학생이 없다면 소거법에 의해 시이가 범인이므로 swi를 출력한다.
입력
첫 번째 줄에 시이의 케이크가 없어졌다는 메시지 (swi's cake is missing!)가 주어진다.
두 번째 줄에 기숙사에 있었던 시이가 아닌 학생의 수 $N$이 주어진다.
$N$명의 학생의 증언이 각각 세 줄에 걸쳐 $N$개 주어진다. $i$번째 증언을 한 학생의 번호는 $i$이다. 각 증언은 아래와 같은 형식으로 이루어져 있다.
- 첫 번째 줄에 명단 $S$에 등장하는 학생의 수 $M$이 주어진다.
- 두 번째 줄에 명단 $S$에 등장하는 학생의 번호 $S_1,S_2,\cdots,S_M$이 중복없이 공백으로 구분되어 주어진다.
- 세 번째 줄에 진술의 유형을 나타내는 정수 $B$가 주어진다. 범인이 있다는 진술이라면 $B=1$, 없다는 진술이라면 $B=0$이다.
출력
모든 진술을 토대로 범인일 가능성이 있는 모든 학생의 번호를 작은 번호부터 순서대로 공백으로 구분하여 출력한다.
만약 범인일 가능성이 있는 학생이 한 명도 없다면 이번에도 시이가 케이크를 먹어버린 것이므로 swi를 출력한다.
제한
- $1 \le N \le 100 \, 000$
- $1 \le M \le N$
- $1 \le S_i \le N$
- 명단에 등장하는 학생 수의 합은 $200\,000$을 넘지 않는다.
예제 입력 1
swi's cake is missing! 2 2 1 2 1 2 1 2 1
예제 출력 1
swi
예제 입력 2
swi's cake is missing! 2 2 1 2 0 1 1 1
예제 출력 2
1
예제 입력 3
swi's cake is missing! 2 1 1 0 1 2 0
예제 출력 3
1 2
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호