| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 60 | 26 | 25 | 45.455% |
부대 창설행사의 인원 모집이 조금 전 마무리되었다!
부대 창설행사는 1ドル$번부터 $N$번까지 총 $N$개의 무대로 구성되며, $P$명의 병사가 참여한다. 병사들은 각자 하나 이상의 희망 무대를 선정한 상태이다.
성공적인 행사를 위해선 무대마다 정해진 최소 인원수를 만족해야 한다. 그러나 인원을 세심하게 분배할 여유가 없기 때문에, 우선 무대 순서를 확정한 뒤 해당 무대를 희망했던 병사들을 무대에 세울 예정이다. 다만, 모든 병사는 연습에 집중하기 위해 본인이 희망한 가장 앞 순서의 무대에만 참여한다.
행사가 성공할 수 있는 순서를 찾고, 그중 하나를 출력하라.
첫 번째 줄에 무대의 수 $N$과 병사의 수 $P$가 공백으로 구분되어 정수로 주어진다.
두 번째 줄에 각 무대의 최소 인원수 $m_i$가 1ドル$번 무대부터 $N$번 무대까지 공백으로 구분되어 정수로 주어진다.
이후 $P$줄에 걸쳐 해당 병사가 희망하는 무대의 수 $x_i$와 $x_i$개의 오름차순으로 정렬된 희망 무대 번호가 공백으로 구분되어 정수로 주어진다.
모든 무대의 최소 인원수를 충족시킬 수 있는 순서가 있다면, $N$줄에 걸쳐 가능한 순서 중 하나를 출력한다.
가능한 순서가 존재하지 않는다면, -1을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | $N = 3;$ $P \le 200$ |
| 2 | 45 | $N \le 8;$ $P \le 200$ |
| 3 | 125 | $N \le 200;$ $P \le 1,000円$ |
| 4 | 50 | 추가 조건 없음 |
3 5 1 1 1 3 1 2 3 3 1 2 3 3 1 2 3 3 1 2 3 3 1 2 3
-1
어떤 무대를 처음으로 세우더라도, 이후 두 번째 무대에 세울 병사가 없어 실패하게 된다.
3 5 1 2 1 2 1 3 1 2 1 1 2 1 2 2 2 3
2 3 1
2번 무대를 2, 4, 5번 병사가 구성한 뒤, 3번 무대를 1번 병사가 구성하며, 마지막으로 1번 무대를 3번 병사가 구성하게 된다.
3 2 1도 성공적인 무대 구성임에 유의하라.
4 15 2 3 3 3 2 1 4 1 3 1 3 1 1 2 2 4 2 1 2 1 2 2 2 4 3 1 2 4 1 2 2 1 3 2 1 4 2 3 4 3 2 3 4 1 3
2 4 1 3
Contest > 보라매컵 > 제2회 보라매컵 예선 D번