在这一部分,保证每行中不存在某一个正数出现超过 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。
RangeSolution
第一问可以优化,如果第 i 个人的第 j 级志愿不能增广,就直接把这些边删掉。
第二问只需要对于每一个人二分答案 $ans_i$ ,把 $ans_i$ 之前的人全部按照最优方案建出图,然后额外的连上第 i 个人所期望的边,再寻找增广路,就可以完美解决第二问。