[八省联考2018] 劈配 mentor (2)

在这一部分，保证每行中不存在某一个正数出现超过 C 次（0 可能出现超 过C 次），同时保证所有$a_{i,j}$​ <= m。

第n + 3 行n 个用空格隔开的正整数，其中第i 个整数为$s_i$​ 。

$s_i$ 表示编号为i 的选手的理想值。

在这一部分，保证$s_i$ <= m。

Output

按顺序输出每组数据的答案。对于每组数据，输出2 行：

第1 行输出n 个用空格隔开的正整数，其中第i 个整数的意义为：

在最优的录取方案中，编号为i 的选手会被该档志愿录取。

特别地，如果该选手出局，则这个数为m + 1。

第 2 行输出 n 个用空格隔开的非负整数，其中第 i 个整数的意义为：

使编号为i 的选手不沮丧，最少需要让他上升的排名数。

特别地，如果该选手一定会沮丧，则这个数为i。

Range

Solution

第一问可以优化，如果第 i 个人的第 j 级志愿不能增广，就直接把这些边删掉。

第二问只需要对于每一个人二分答案 $ans_i$​ ，把 $ans_i$​​ 之前的人全部按照最优方案建出图，然后额外的连上第 i 个人所期望的边，再寻找增广路，就可以完美解决第二问。