시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)218857340.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)$

각 줄의 처음에는 해당 스터디 그룹에 배정된 사람의 수, 그리고 이어서 배정된 사람의 번호를 공백으로 구분하여 출력한다.

답이 여러 개 존재하면 아무거나 출력해도 되며, 배정된 사람의 번호를 출력하는 순서는 무관하다.

제한

  • $1\leq N,K,X\leq 15$
  • $1\leq K\times X\leq 15$
  • $1\leq C_i\leq K$
  • $1\leq A_{i,j}\leq K$ $(1\le i\le N,1\le j\le C_i)$
  • $j\ne k$ 이면 $A_{i,j}\ne A_{i,k}$이다. $(1\le i\le N,1\le j,k\le C_i)$ 즉, 각 행의 원소는 모두 서로 다르다.
  • $1\leq B_i\leq 10^9$ $(1\le i\le N)$
  • $i\ne j$ 이면 $B_i\ne B_j$이다. $(1\le i,j\le N)$ 즉, $B$의 원소는 모두 서로 다르다.
  • 입력으로 주어지는 수는 모두 정수이다.

예제 입력 1

5 2 2
1 1
2 1 2
1 1
1 1
1 2
5 4 3 2 1

예제 출력 1

2 1 3
2 2 5

출처

University > 숭실대학교 > 2023 SCON H번