問題一覧 > 通常問題

No.2680 Laboratory Assignment

レベル : / AI推定難易度 : 450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 135
作問者 : kjqw / テスター : SPD_9X2 👑 rin204 だれ arad kyawa ma_tw Ayuna sakuraajisai
お気に入りにしたユーザー ProblemId : 10429 / 自分の提出
問題文最終更新日: 2024-03-20 18:32:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 422 (第1回 競技プログラミング講習会作問企画コンテスト) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。