#2477. 「九省联考 2018」劈配

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一年一度的综艺节目《中国新代码》又开始了。Zayid 从小就梦想成为一名程序员,他觉得这是一个展示自己的舞台,于是他毫不犹豫地报名了。

轻车熟路的 Zayid 顺利地通过了海选,接下来的环节是导师盲选,这一阶段的规则是这样的: 总共 nn 名参赛选手(编号从 11nn)每人写出一份代码并介绍自己的梦想。接着由所有导师对这些选手进行排名。为了避免后续的麻烦,规定不存在排名并列的情况。

同时,每名选手都将独立地填写一份志愿表,来对总共 mm 位导师(编号从 11mm)作出评价。志愿表上包含了共 mm 档志愿。对于每一档志愿,选手被允许填写最多 CC 位导师,每位导师最多被每位选手填写一次(放弃某些导师也是被允许的)。

在双方的工作都完成后,进行录取工作。每位导师都有自己战队的人数上限,这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。

节目组对 ‘‘前 ii 名的录取结果最优’’ 作出如下定义:

  • 11 名的录取结果最优,当且仅当第 11 名被其最高非空志愿录取(特别地,如果第 11 名没有填写志愿表,那么该选手出局)。
  • ii 名的录取结果最优,当且仅当在前 i1i − 1 名的录取结果最优的情况下:第 ii 名被其理论可能的最高志愿录取(特别地,如果第 ii 名没有填写志愿表、或其所有志愿中的导师战队均已员,那么该选手出局)。

如果一种方案满足 ‘‘前 nn 名的录取结果最优’’,那么我们可以简称这种方案是最优的。

举例而言,22 位导师 T 老师、F 老师的战队人数上限分别都是 11 人;22 位选手 Zayid、DuckD 分列第 1122 名。那么下面 33 种志愿表及其对应的最优录取结果如表中所示:

选手11 志愿22 志愿录取志愿加入战队
ZayidN/AT 老师、F 老师2F 老师
DuckDT 老师F 老师1T 老师
选手11 志愿22 志愿录取志愿加入战队
ZayidT 老师F 老师1T 老师
DuckDT 老师F 老师2F 老师
选手11 志愿22 志愿录取志愿加入战队
ZayidF 老师N/A1F 老师
DuckDF 老师N/A出局N/A

可以证明,对于上面的志愿表,对应的方案都是唯一的最优录取结果。 每个人都有一个自己的理想值 sis_i,表示第 ii 位同学希望自己被第 sis_i 或更高的志愿录 取,如果没有,那么他就会非常沮丧。 现在,所有选手的志愿表和排名都已公示。巧合的是,每位选手的排名都恰好与它 们的编号相同。 对于每一位选手,Zayid 都想知道下面两个问题的答案:

  • 在最优的录取方案中,他会被第几志愿录取。
  • 在其他选手相对排名不变的情况下,至少上升多少名才能使得他不沮丧。 作为《中国新代码》的实力派代码手,Zayid 当然轻松地解决了这个问题。不过他 还是想请你再算一遍,来检验自己计算的正确性。

输入格式

每个测试点包含多组测试数据,第一行 22 个用空格隔开的非负整数 TT,CC,分别表示 数据组数、每档志愿最多允许填写的导师数目。

接下来依次描述每组数据,对于每组数据:

  • 11 行两个用空格隔开的正整数 nn, mm
    • nn, mm 分别表示选手的数量、导师的数量。
  • 22mm 个用空格隔开的正整数:其中第 ii 个整数为 bib_i
    • bib_i 表示编号为 ii 的导师战队人数的上限。
  • 33 行至第 n+2n + 2 行,每行 mm 个用空格隔开的非负整数:其中第 i+2i + 2 行左起第 jj 个数为 ai,ja_{i, j}
    • ai,ja_{i, j} 表示编号为 ii 的选手将编号为 jj 的导师编排在了第 ai,ja_{i, j} 志愿。特别地,如果 ai,j=0a_{i, j} = 0,则表示该选手没有将该导师填入志愿表。
    • 在这一部分,保证每行中不存在某一个正数出现超过 CC 次(00 可能出现超过 CC 次),同时保证所有 ai,jma_{i, j} \le m
  • n+3n + 3nn 个用空格隔开的正整数,其中第 ii 个整数为 sis_i
    • sis_i 表示编号为 ii 的选手的理想值。
    • 在这一部分,保证 sims_i \le m

输出格式

按顺序输出每组数据的答案。对于每组数据,输出 22 行:

  • 11 行输出 nn 个用空格隔开的正整数,其中第 ii 个整数的意义为:
    • 在最优的录取方案中,编号为 ii 的选手会被该档志愿录取。
    • 特别地,如果该选手出局,则这个数为 m+1m + 1
  • 22 行输出 nn 个用空格隔开的非负整数,其中第 ii 个整数的意义为:
    • 使编号为 ii 的选手不沮丧,最少需要让他上升的排名数。
    • 特别地,如果该选手一定会沮丧,则这个数为 ii

样例

样例 1 输入

3 5
2 2
1 1
2 2
1 2
1 1
2 2
1 1
1 2
1 2
2 1
2 2
1 1
0 1
0 1
2 2

样例 1 输出

2 1
1 0
1 2
0 1
1 3
0 1

样例 1 解释

三组数据分别与「题目描述」中的三个表格对应。

对于第 11 组数据:由于选手 11 没有填写第一志愿,所以他一定无法被第一志愿录 取,也就一定会沮丧。选手 22 按原排名就不沮丧,因此他不需要提升排名。 对于第 22 组和第 33 组数据:11 号选手都不需要提升排名。而希望被第一志愿录取的 22 号选手都必须升到第 11 名才能如愿。

样例 2 输入

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

样例 2 输出

1 1 3 2
0 0 0 0

样例 2 解释

11 号选手的第一志愿只填写了 22 号导师,因此 11 号选手必定被 22 号导师录取。 22 号选手的第一志愿只填写了 33 号导师,因此 22 号选手必定被 33 号导师录取。 由于 2,32, 3 号导师均满员,且 3,43, 4 号选手均填写了 11 号导师,因此它们都会被 11 号导 师录取。 所以 1,21, 2 号选手均被第 11 志愿录取,33 号选手被第 33 志愿录取,44 号选手被第 22 志 愿录取。 由于他们都如愿以偿了,所以他们都不需要提升名次。

样例 3

见附加文件中的 mentor/mentor3.in 与 mentor/mentor3.ans。

样例 4

见附加文件中的 mentor/mentor4.in 与 mentor/mentor4.ans。

数据范围与提示

测试点编号nn \lemm \leCC其他约定
11101011=1=1
22101022=2=2si=ms_i=m
33101033=3=3
44100100100100=1=1bi=1b_i=1
55100100100100=1=1
66200200200200=1=1bi=1b_i=1
77200200200200=1=1
88100100100100=10=10
99200200200200=10=10bi=1b_i=1
1010200200200200=10=10

对于所有测试点,保证 T5T \le 5

对于所有测试点中的所有数据,保证 mn200m \le n \le 200binb_i \le n