| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 218 | 85 | 73 | 40.556% |
SCCC의 회장인 찬솔이는 2023년 1학기 신입 부원 선발 과정을 진행하고 있다. SCCC는 2023년 1학기에 정원이 $X$명인 스터디 그룹을 $K$개 운영하고, 이번 학기에 새로 들어오는 신입 부원들은 $K$개의 스터디 그룹 중 정확히 하나의 그룹에 참가해야 한다. 참가할 수 있는 스터디 그룹이 없으면 합격할 수 없으므로 모든 지원자는 본인이 참가할 수 있는 스터디 그룹을 한 개 이상 선택했다.
찬솔이는 공정하고 엄격한 심사를 통해 $N$명의 지원자들에게 서로 다른 점수를 매겼다. 이제 신입 부원들을 스터디에 배정하기 위해 점수가 높은 사람에서 낮은 사람 순으로 정렬한 다음, 한 명씩 스터디 그룹에 배정하려고 한다.
구체적으로, 점수가 $i$번째로 높은 사람을 스터디 그룹에 배정하려고 하는 상황을 생각해 보자. 만약 지금까지 스터디에 배정된 사람들의 집합을 유지하면서 $i$번째 사람을 스터디에 넣을 수 있으면 $i$번째 사람을 스터디에 배정한다. 반대로, 지금까지 스터디에 배정된 사람들을 어떻게 이동시키더라도 $i$번째 사람이 들어갈 수 있는 자리가 없다면 $i$번째 사람을 스터디에 배정될 수 없다.
예를 들어 $N=5,K=2,X=2$이고, 점수가 높은 사람부터 각 지원자가 참가할 수 있는 스터디 그룹이 $\{1\} ,\{1,2\} ,\{1\} ,\{1\} ,\{2\}$라고 하자.
점수가 가장 높은 사람과 두 번째로 높은 사람이 모두 $1$번 그룹에 배정되었고, 세 번째로 높은 사람을 배정해야 하는 상황을 생각해 보자. 두 번째 사람의 스터디 그룹을 $2$번 그룹으로 옮긴 뒤 세 번째 사람을 $1$번 그룹에 배정하면, 이전까지 스터디에 배정된 사람들의 집합을 유지하면서 세 번째 사람을 스터디에 넣을 수 있다.
반면, $1$번 그룹에 첫 번째와 세 번째 사람, $2$번 그룹에 두 번째 사람이 배정된 상황에서 네 번째 사람을 배정할 방법은 존재하지 않는다. 하지만 점수가 가장 낮은 사람은 $2$번 그룹에 들어갈 수 있으므로 최종 결과는 $1$번 그룹에 첫 번째와 세 번째 사람, $2$번 그룹에 두 번째 사람과 다섯 번째 사람이 배정되는 것이다.
찬솔이는 이 규칙에 따라 지원자들을 스터디 그룹에 배정하려고 한다. 이때 스터디 그룹에 배정되는 사람의 수와, 각 스터디 그룹에 배정된 지원된 사람의 목록을 구해야 한다. 신입 부원 선발 외에도 많은 일을 처리해야 하는 찬솔이를 위해 스터디 배정 프로그램을 대신 작성해 주자.
첫째 줄에 지원자 수 $N$, 스터디 그룹의 개수 $K$, 각 스터디 그룹의 정원 $X$가 공백으로 구분되어 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 지원자의 정보가 주어진다. $(1\le i\le N)$
지원자의 정보는 한 줄로 구성되어 있다. 각 줄의 처음에는 참가할 수 있는 스터디의 개수 $C_i$가 주어지고, 이어서 참가할 수 있는 $C_i$개의 스터디 그룹의 번호 $A_{i,1},A_{i,2},\cdots ,A_{i,C_i}$가 공백으로 구분되어 주어진다.
$N+2$번째 줄에는 각 학생의 점수 $B_1,B_2,\cdots ,B_N$이 공백으로 구분되어 주어진다.
첫째 줄부터 $K$개의 줄에 걸쳐, $i$번째 줄에 $i$번 그룹에 배정된 사람의 정보를 출력한다. $(1\le i\le K)$
각 줄의 처음에는 해당 스터디 그룹에 배정된 사람의 수, 그리고 이어서 배정된 사람의 번호를 공백으로 구분하여 출력한다.
답이 여러 개 존재하면 아무거나 출력해도 되며, 배정된 사람의 번호를 출력하는 순서는 무관하다.
5 2 2 1 1 2 1 2 1 1 1 1 1 2 5 4 3 2 1
2 1 3 2 2 5