시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 19 6 (32%) 2
문제
KOI 측으로부터 업무를 위탁 받은 CEOI는 오늘부터 N일 동안 M개의 업무를 모두 완료해야 한다. 하나의 업무를 완료하기 위해서는 정확히 하나의 기계가 하루 동안 일해야 한다. CEOI는 몇 대의 기계들을 사용할 수 있고, 각 기계는 하루에 최대 한 번 작동할 수 있다. 즉, CEOI가 하루에 완료할 수 있는 업무의 최대 개수는 사용 가능한 기계의 개수와 똑같다. KOI 측에서는 $S_i$일에 업무 $i$를 CEOI에게 위탁하였다. $S_i$일에 업무를 전해받은 CEOI는 D일의 지연은 감수하여 $S_i + D$일까지는 꼭 완료하기로 했다. CEOI가 각각의 업무를 $D$일 이하로 지연되도록 하면서 모든 업무를 완료할 수 있도록 하는 기계들의 최소 개수를 구하는 프로그램을 작성하라.
입력
표준 입력에서 다음의 입력을 읽는다. 첫 번째 줄에 세 정수 $N, D, M$이 주어진다. $N(1 \leq N \leq 100,000)$은 CEOI가 업무를 처리하는 전체 일수, $D(0 \leq D < N)$는 각의 업무가 지연될 수 있는 최대 일 수, $M(1 \leq M \leq 1,000,000)$은 전체 업무의 개수를 나타낸다. 두 번째 줄에는 정확히 M개의 정수가 빈 칸을 사이에 두고 주어진다. $i$번째 숫자는 업무 $i$의 위탁 날짜(즉, CEOI가 업무를 전해받은 날짜) $S_i$를 나타낸다. 날짜는 1부터 $N$까지의 정수로 표현된다. $S_i$가 $N-D$보다 늦은 경우는 없다.
출력
표준 출력으로 다음을 출력한다. 첫 번째 줄에 각각의 업무를 $D$일 이하로 지연되도록 하면서 모든 업무를 완료할 수 있도록 하는 기계들의 최소 개수를 출력한다. 다음 N개의 줄에 실제 작업 스케쥴을 출력한다. $i+1$번째 줄에는 $i$번째 날에 완료할 업무들을 빈 칸을 사이에 두고 출력하고 마지막에는 0을 출력한다. 만약 가능한 작업 스케쥴이 여러 가지가 있다면 아무 것이나 출력하면 된다.
힌트
다음 항목들에 대하여 부분점수를 받을 수 있다. - 테스트 케이스의 50%는 M이 100,000 이하이다. - 출력의 첫 번째 줄만 맞은 경우는 원래 점수의 40%를 받을 수 있다. #### 입력 예시 ``` 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4 ``` #### 출력 예시 ``` 2 5 1 0 9 4 0 2 10 0 6 12 0 3 7 0 11 8 0 0 0 ```