#P18759. [2027年国家集训队互测] Task Scheduling
[2027年国家集训队互测] Task Scheduling
Task Scheduling
题目描述
一台机器上,有 个无依赖关系的任务等待被调度。在 时刻启动执行的任务,会在 时刻完成。所有任务只能在整数时刻启动;一个任务完成时,可以立即启动另一个任务。在一个任务执行的过程中,无法执行别的任务。
任务具有时效性。可以被表示为:第 个任务的启动时刻,必须在 时刻到 时刻(包含两边)之间。
此外,还有 条约束。第 个约束表示,在 时刻到 时刻(包含两边)之间,最多只能启动一个任务。
请确定每个任务的启动时刻,满足上述要求。
输入格式
本题包含多组测试数据。
输入的第一行包含非负整数 ,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据:
-
第一行包含两个整数 和 。
-
接下来 行,每行两个整数 和 ,表示第 个任务的可用时间区间。
-
接下来 行,每行两个整数 和 ,表示第 个调度约束区间。
输出格式
对于每组数据,输出一行 个整数,依次表示每个任务的启动时刻。特别地,若不存在可行方案,则输出 Impossible。若存在多组可行方案,输出任意一组即可。
样例一
样例输入
4
2 3
2 7
1 10
7 8
2 10
1 6
2 2
2 5
1 9
1 5
4 9
2 4
3 8
3 6
2 7
4 7
8 9
1 6
4 1
6 7
6 7
6 7
1 11
21 31
样例输出
7 1
3 9
8 6
Impossible
说明
本样例满足子任务 的限制。
-
对于第一组数据,两个任务分别在时刻 启动。均在各自的 范围内,且满足所有约束。
-
对于第四组数据,前三个任务都只能在时刻 或 启动。故不存在可行的方案。
样例二
见下发文件中的 ex_data2.in 和 ex_data2.ans。
本样例满足子任务 的限制。
样例三
见下发文件中的 ex_data3.in 和 ex_data3.ans。
本样例满足子任务 的限制。
样例四
见下发文件中的 ex_data4.in 和 ex_data4.ans。
本样例满足子任务 的限制。
样例五
见下发文件中的 ex_data5.in 和 ex_data5.ans。
本样例满足子任务 的限制。
样例六
见下发文件中的 ex_data6.in 和 ex_data6.ans。
本样例满足子任务 的限制。
样例七
见下发文件中的 ex_data7.in 和 ex_data7.ans。
本样例满足子任务 的限制。
样例八
见下发文件中的 ex_data8.in 和 ex_data8.ans。
本样例满足子任务 的限制。
数据范围
设 分别为单个测试点内所有测试数据的 的和。对于所有测试数据,均有:
-
$1 \le n \le 2.5 \times 10^5,0 \le m \le 2.5 \times 10^5$;
-
;
-
。
| 子任务编号 | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 无 | ||||
| 无 | ||||
:保证 ,且对于所有 ,均有 ,。
:对于所有 ,均有 。
:对于所有 ,均有 ,且对于所有 ,均有 。
完整样例附件
全部 8 份样例见 样例 ZIP 附件,也可查看 所有样例。附件中的 .ans 为一组合法输出,答案不唯一。
是非负整数, 合法,此时无需输出。所有输入均满足 。