問題一覧 > 通常問題

No.2680 研究室配属

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 116
作問者 : kjqwkjqw / テスター : 👑 SPD_9X2SPD_9X2 👑 rin204rin204 だれだれ aradarad kyawakyawa ma_twma_tw AyunaAyuna sakuraajisaisakuraajisai
0 ProblemId : 10429 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-20 18:32:34

問題文

$N$ 人の学生を $M$ 個の研究室に割り当てることを考えます。
研究室には $0$ から $M-1$ までの番号がつけられており、研究室 $i$ の定員は $A_{i}$ 人です。
学生は成績が良い順に番号付けされ、$j+1$ 番目に成績が良い学生(学生 $j$)の第$k+1$希望の研究室は $T_{j,k}$ です。
以下のルールに従って全ての学生を研究室に割り当てます。その結果を求めてください。

(1) 全ての学生を第1希望の研究室に仮に割り当てる。
(2) 定員を超えた研究室については成績が悪い学生から順に仮割り当てを外していき、定員まで減らす。
(3) 仮で割り当てられている学生の配属が確定される。
(4) 第1希望の研究室に配属できなかった全ての学生を、第2希望の研究室に仮に割り当てる。
(5) (2), (3)を行い、第2希望の研究室に配属できなかった全ての学生を、 第3希望の研究室に仮に割り当てる。
(6) (2), (3)を行い、第3希望の研究室に配属できなかった全ての学生を、 第4希望の研究室に仮に割り当てる。
$\vdots\\$ この操作を全ての学生の配属が確定するまで繰り返す。

なお、この問題の制約下において全ての学生の配属が確定することが証明できます。

入力

$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}$

  • 入力は全て整数$\\$
  • $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}$ は $0,1, \cdots M-1$ の順列

出力

各学生が配属された研究室の番号を、成績が良い順にスペース区切りで出力してください。 最後に改行してください。

サンプル

サンプル1
入力
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
出力
0 0 1 2 1 2 1 2

学生0, 1は第1希望の研究室0に配属され、研究室0の募集は締め切られるため、 学生2, 3, 6は第1希望の研究室0に入れません。 学生4は研究室1、学生5は研究室2、学生7は研究室2にそれぞれ配属され、 研究室1の空きは2、研究室2の空きは1となります。 学生2, 3, 6の第2希望の研究室は1, 2, 1ですが、学生3が研究室2に入ると 研究室2の募集は締め切られるため、学生6は第2希望の研究室に配属されず、 第3希望の研究室1に配属されることとなります。

サンプル2
入力
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
出力
0 2 2 1 1 2 2 1 2

サンプル3
入力
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
出力
5 1 1 0 5 4 3 5 2 2 4 5 2 3 5 3 5 4 3 4 4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。