#PQJ4603x21433. QOJ 4603_21433
QOJ 4603_21433
标题: 任务调度 - Problem - QOJ.ac
#21433. 任务调度
The problem was used in the following contests:
题目描述
一台机器上,有 n 个无依赖关系的任务等待被调度。在 t 时刻启动执行的任务,会在 t+1 时刻完成。所有任务只能在整数时刻启动;一个任务完成时,可以立即启动另一个任务。在一个任务执行的过程中,无法执行别的任务。
任务具有时效性。可以被表示为:第 i 个任务的启动时刻,必须在 li 时刻到 ri 时刻(包含两边)之间。
此外,还有 m 条约束。第 j 个约束表示,在 pj 时刻到 qj 时刻(包含两边)之间,最多只能启动一个任务。
请确定每个任务的启动时刻,满足上述要求。
输入格式
本题包含多组测试数据。
输入的第一行包含非负整数 T,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据:
- 第一行包含两个整数 n 和 m。
- 接下来 n 行,每行两个整数 li 和 ri,表示第 i 个任务的可用时间区间。
- 接下来 m 行,每行两个整数 pj 和 qj,表示第 j 个调度约束区间。
输出格式
对于每组数据,输出一行 n 个整数,依次表示每个任务的启动时刻。特别地,若不存在可行方案,则输出 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
说明
本样例满足子任务 1 的限制。
- 对于第一组数据,两个任务分别在时刻 7,1 启动。均在各自的 [l,r] 范围内,且满足所有约束。
- 对于第四组数据,前三个任务都只能在时刻 6 或 7 启动。故不存在可行的方案。
样例二
见下发文件中的 ex_data2.in 和 ex_data2.ans。
本样例满足子任务 2 的限制。
样例三
见下发文件中的 ex_data3.in 和 ex_data3.ans。
本样例满足子任务 3 的限制。
样例四
见下发文件中的 ex_data4.in 和 ex_data4.ans。
本样例满足子任务 4 的限制。
样例五
见下发文件中的 ex_data5.in 和 ex_data5.ans。
本样例满足子任务 5 的限制。
样例六
见下发文件中的 ex_data6.in 和 ex_data6.ans。
本样例满足子任务 6 的限制。
样例七
见下发文件中的 ex_data7.in 和 ex_data7.ans。
本样例满足子任务 7 的限制。
样例八
见下发文件中的 ex_data8.in 和 ex_data8.ans。
本样例满足子任务 8 的限制。
数据范围
设 N,M 分别为单个测试点内所有测试数据的 n,m 的和。对于所有测试数据,均有:
- 1≤n≤2.5×105,0≤m≤2.5×105;
- 1≤li≤ri≤109;
- 1≤pj≤qj≤109。
子任务编号 N≤ M≤ 特殊性质 分值 1 10 10 无 5 2 2.5×105 2.5×105 A 5 3 103 103 B 15 4 2.5×105 2.5×105 C 15 5 104 104 B 15 6 105 105 B 15 7 105 105 无 15 8 2.5×105 2.5×105 无 15
A:保证 n≤100,且对于所有 1≤i<n,均有 li≤li+1,ri≤ri+1。
B:对于所有 1≤i≤n,均有 ri≤5max(n,m)。
C:对于所有 1≤i≤m,均有 pi=i,qi=i+1,且对于所有 1≤i≤n,均有 ri≤m。