| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 157 | 98 | 81 | 61.364% |
DGIST의 교수로 재직중인 달구 교수님은 운영체제 과목을 담당하고 있다. 달구 교수님은 시험 문제 출제를 위해 열심히 고민 중이다. 이번 시험은 교과서 내용으로만 출제하며, 시험 범위는 교과서의 $1$번 챕터부터 $M$번 챕터까지, 총 $M$개 챕터이다.
달구 교수님은 $N$ 명의 수강생이 각각 어떤 챕터들을 공부했는지 파악했다. 학생들은 공부한 챕터에서 문제가 출제되면 반드시 맞히며, 공부하지 않은 챕터에서 문제가 출제되면 반드시 틀린다.
달구 교수님은 이번 시험에서 동일한 점수를 받는 학생이 없도록, 각 챕터의 배점을 설정하고자 한다. 단, 각 챕터의 배점은 $1$ 이상 $10^{9}$ 이하의 정수여야 한다. 달구 교수님을 도와, 모든 학생이 서로 다른 점수를 받도록 각 챕터에 배정할 배점을 구하시오. 배정 가능한 배점이 여러 가지인 경우에는 그 중 아무거나 출력하시오.
첫째 줄에 수강생 수 $N$과 시험 범위 챕터 수 $M$이 공백으로 구분되어 정수로 주어진다. ($1 \le N \le 200\,000$, $1 \le M \le 30$)
다음 $N$개의 줄에 걸쳐, 각 수강생이 공부한 챕터에 대한 정보가 주어진다. 각 줄은 해당 학생이 공부한 챕터의 개수 $x_i$ ($0 \le x_i \le M$)로 시작하며, 이후 해당 학생이 공부한 $x_i$개의 서로 다른 챕터 번호를 의미하는 정수 $y_{ij}$ ($1 \le y_{ij} \le M$)가 공백으로 구분되어 오름차순으로 주어진다.
모든 학생이 서로 다른 점수를 받도록 하는 각 챕터의 배점을 $1$번 챕터부터 $M$번 챕터까지 순서대로 공백으로 구분하여 출력하시오. 배정 가능한 배점이 여러 가지인 경우에는 그 중 아무거나 출력하시오. 만약 배점을 어떻게 배정하더라도 점수가 동일한 학생이 발생한다면, -1을 출력하시오.
3 2 2 1 2 0 1 2
1 2
챕터 $1$에서 $1$점, 챕터 $2$에서 $2$점 배점의 문제를 출제하면, 첫 번째 학생은 $3$점, 두 번째 학생은 $0$점, 세 번째 학생은 $2$점을 획득한다.
챕터 $1$에서 $2$점, 챕터 $2$에서 $1$점 배점의 문제를 출제해도 문제의 조건에 만족하므로, 정답으로 처리된다.
3 3 3 1 2 3 3 1 2 3 3 1 2 3
-1
어떻게 배점을 배정하더라도 모든 학생이 만점을 받게 된다.
입력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 다음과 같습니다.
cin을 사용하여 입력받는 경우, ios::sync_with_stdio(false); cin.tie(NULL); 를 적용해야 합니다.BufferedReader와 BufferedWriter를 사용해야 합니다.input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.University > DGIST > 2025 DGIST 알고리즘 경진대회 C번