No.2680 Laboratory Assignment
Problem Statement
Consider assigning $N$ students to $M$ laboratories.
The laboratories are numbered from $0$ to $M-1$, and the capacity of laboratory $i$ is $A_{i}$ students.
The students are numbered in descending order of grades, and the laboratory that is the $k+1$-th choice of the student with the $j+1$-th best grades (student $j$) is $T_{j,k}$.
All students are assigned to laboratories according to the following rules. Find the result.
(1) Tentatively assign all students to their 1st-choice laboratories.
(2) For each laboratory over capacity, remove tentative assignments in order starting from the student with the worst grades, until the number of students is reduced to the capacity.
(3) The assignments of the tentatively assigned students become final.
(4) Tentatively assign all students who could not be assigned to their 1st-choice laboratories to their 2nd-choice laboratories.
(5) Perform (2), (3), then tentatively assign all students who could not be assigned to their 2nd-choice laboratories
to their 3rd-choice laboratories.
(6) Perform (2), (3), then tentatively assign all students who could not be assigned to their 3rd-choice laboratories
to their 4th-choice laboratories.
$\vdots\\$
Repeat this operation until the assignments of all students are final.
It can be proved that, under the constraints of this problem, the assignments of all students become final.
Input
$N\ M$
$A_{0}\ A_{1}\ A_{2}\ \cdots\ A_{M-1}$
$T_{0,0}\ T_{0,1}\ \cdots\ T_{0,M-1}$
$T_{1,0}\ T_{1,1}\ \cdots\ T_{1,M-1}$
$\vdots$
$T_{N-1,0}\ T_{N-1,1}\ \cdots\ T_{N-1,M-1}$
- All inputs are integers$\\$
- $1 \leq M \leq N \leq 1000$
- $0 \le A_i$
- $\displaystyle \sum_{i=0}^{M-1} A_i = N$
- $T_{j,0},T_{j,1}, \cdots ,T_{j,M-1}$ is a permutation of $0,1, \cdots M-1$
Output
Print the number of the laboratory to which each student is assigned, in descending order of grades, separated by spaces. Print a newline at the end.
Sample
Sample 1
Input
8 3 2 3 3 0 1 2 0 2 1 0 1 2 0 2 1 1 0 2 2 1 0 0 2 1 2 0 1
Output
0 0 1 2 1 2 1 2
Students 0, 1 are assigned to laboratory 0, their 1st choice, and laboratory 0 stops accepting students, so students 2, 3, 6 cannot enter laboratory 0, their 1st choice. Student 4 is assigned to laboratory 1, student 5 to laboratory 2, and student 7 to laboratory 2, leaving 2 open spots in laboratory 1 and 1 open spot in laboratory 2. The 2nd-choice laboratories of students 2, 3, 6 are 1, 2, 1, but when student 3 enters laboratory 2, laboratory 2 stops accepting students, so student 6 is not assigned to their 2nd-choice laboratory and is instead assigned to laboratory 1, their 3rd choice.
Sample 2
Input
9 3 1 3 5 0 1 2 0 1 2 0 1 2 1 0 2 1 2 0 0 2 1 0 2 1 1 2 0 1 2 0
Output
0 2 2 1 1 2 2 1 2
Sample 3
Input
21 6 1 2 3 4 5 6 5 3 4 0 1 2 1 2 4 5 3 0 1 4 0 3 2 5 0 4 1 5 2 3 5 4 2 0 1 3 0 1 4 2 3 5 1 3 4 5 0 2 5 1 2 0 4 3 0 1 2 4 5 3 0 2 4 3 5 1 0 1 4 3 2 5 5 3 1 2 4 0 2 3 1 0 5 4 3 0 1 5 2 4 0 5 4 1 2 3 3 2 4 0 1 5 5 3 2 1 4 0 0 3 1 5 2 4 3 1 5 2 0 4 1 0 4 2 5 3 1 3 2 4 5 0
Output
5 1 1 0 5 4 3 5 2 2 4 5 2 3 5 3 5 4 3 4 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SPD_9X2
だれ
arad
kyawa
Ayuna