시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 122 | 21 | 20 | 21.277% |
선린인터넷고등학교에는 $N$명의 학생들이 있다. $N$명의 학생들 가운데 일부는 서로를 좋아한다. 신기한 사실이 있는데, 학생들 간에 일방적으로 좋아하는 경우는 없고, 반드시 서로 좋아하거나, 혹은 서로 좋아하지 않는다고 한다.
어느 날, $N$명의 학생들이 둥근 원탁 위에 앉아 식사를 하고자 한다. 원탁 주위에는 $N$개의 자리가 있으며, 위 그림과 같이 원형으로 배치되어 있다.
어떤 학생이 자리 배치를 만족스럽게 느낄 조건은 자신의 양 옆에 자신이 좋아하는 학생이 앉아있는 것이라 한다. 모든 학생들이 만족스럽게 자리를 배치할 수 있을지 알아보자.
학생 수를 나타내는 정수 $N$이 주어진다. 편의상 학생에 번호를 붙여 생각하자.
각 $i$ ($1 \le i \le N$)에 대해 $i+1$번째 줄에는 $N$개의 정수 $a_{i, 1}, \dots, a_{i, N}$ 이 주어진다. $a_{i, j}$가 $1$이라면 학생 $i$가 학생 $j$를 좋아함을 의미하고, $0$이라면 학생 $i$가 학생 $j$를 좋아하지 않음을 의미한다.
참고로, $a_{i, i} = 0$이며, 문제의 조건에 의해 $a_{i, j} = a_{j, i}$이다.
그리고 각 $i(1 \le i \le N)$에 대해 $\displaystyle \sum_{j=1}^{N} a_{i, j} \ge {N \over 2}$임이 보장된다.
모든 학생이 만족스럽게 자리를 배치할 방법이 존재한다면, $1$번 자리에 앉는 학생의 번호부터 $N$번 자리에 앉는 학생의 번호까지 사이에 공백을 두고 출력하라.
만약 모든 학생이 만족스럽게 자리를 배치할 방법이 존재하지 않는다면, $-1$을 출력하라.
3 0 1 1 1 0 1 1 1 0
2 1 3
어떤 순서로 학생들이 앉든지 상관 없다.
5 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0
2 1 3 4 5
High School > 선린인터넷고등학교 > 2020 선린 정보 알고리즘경시대회 E번