Server Time:

User's AC Ratio in this contest

45.0% (9/20)

Submission's AC Ratio in this contest

22.9% (11/48)

Description

各位上過大學的應該都知道,大學會有通識課程,而通識課程通常是用抽籤決定是否錄取的。
但是學校的抽籤系統被弄壞了,因此你身為學校的工讀生,要幫助學校寫出一份抽籤的系統,
需要根據每一門通識課程的人數上限以及學生的志願序,來為每一名學生抽籤看錄取哪一門通識課。

學校的通識課抽籤方式如下:

  1. 每一位學生僅會抽中一門課。
  2. 若有多人選擇同一門課,但是名額不足時,則將該課程排較前面志願序的人的可以優先錄取,若志願序相同則可以隨意選擇要讓哪位學生錄取。

假設 $A,B,C$ 三門課的名額上限分別為 $1,2,1$,且三位學生 $a,b,c$ 的志願序如下:

$a:A,B$
$b:C,A,B$
$c:C,A$

則不可以將抽籤結果分配為 ${a:B,b:A,c:C}$,因為 $a$ 將課程 $A$ 排第一位,$b$ 將課程 $A$ 排第二位,
卻是 $b$ 錄取課程 $A$,不符合志願序較前面的人優先錄取的原則。

一組合法的抽籤結果為 ${a:A,b:B,c:C}$。

Input Format

第一行輸入兩個整數 $N,M$,分別代表課程的數量以及學生的數量。
第二行輸入 $N$ 個整數,第 $i$ 個數字 $c_i$ 代表課程代碼為 $i$ 的課程之人數上限。
接下來 $M$ 行,每行第一個數字 $K$ 代表該學生填的志願數量,後面有 $K$ 個數字,第 $i$ 個數字 $v_i$ 代表該學生第 $i$ 志願的課程代碼。

  • $1\leq N, M\leq1000$
  • $0\leq c_i\leq M$
  • $0\leq K\leq N$
  • $1\leq v_i\leq N$
  • 同一個人的志願序中不會有重複的課程代碼

Output Format

輸出一行 $M$ 個數字,第 $i$ 個數字代表第 $i$ 位學生錄取的課程之代碼,每個數字間以一個空格隔開,若學生沒有錄取任何課程則輸出 -1。

只要輸出任意一組合法的抽籤結果都會被判為正確。

Sample Input 1

3 3
1 2 1
2 1 2
3 3 1 2
2 3 1

Sample Output 1

1 2 3

Sample Input 2

4 5
1 1 3 2
3 1 2 4
2 2 1
4 2 3 1 4
4 2 4 1 3
1 4

Sample Output 2

1 -1 2 4 4

Hints

此抽籤方式僅為虛構,如有雷同,純屬巧合。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~12 $N,M\leq8$ 45
2 0~28 無特別限制 55

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2
1 1000 65536 65536 1 2
2 1000 65536 65536 1 2
3 1000 65536 65536 1 2
4 1000 65536 65536 1 2
5 1000 65536 65536 1 2
6 1000 65536 65536 1 2
7 1000 65536 65536 1 2
8 1000 65536 65536 1 2
9 1000 65536 65536 1 2
10 1000 65536 65536 1 2
11 1000 65536 65536 1 2
12 1000 65536 65536 1 2
13 1000 65536 65536 2
14 1000 65536 65536 2
15 1000 65536 65536 2
16 1000 65536 65536 2
17 1000 65536 65536 2
18 1000 65536 65536 2
19 1000 65536 65536 2
20 1000 65536 65536 2
21 1000 65536 65536 2
22 1000 65536 65536 2
23 1000 65536 65536 2
24 1000 65536 65536 2
25 1000 65536 65536 2
26 1000 65536 65536 2
27 1000 65536 65536 2
28 1000 65536 65536 2