#P17802. [Ontak2024]REP
[Ontak2024]REP
题目描述
有 个事件,按输入顺序编号 到 。事件 占用时间区间 。
你要选择恰好 个不同事件,使这些区间两两不相交,然后按发生的时间顺序列出所选事件的编号。转移不消耗时间,前一个事件恰好在后一个事件开始时结束是允许的。
在所有长度为 的合法编号序列中,求字典序最小的一个。事件编号不保证与开始或结束时间相关。
给定多个不同或相同的 ,分别回答。各次查询相互独立。
输入格式
第一行整数 ,表示该测试所属的最早子任务编号,。
第二行两个整数 。
接下来 行,第 行两个整数 。
接下来 行,每行一个整数 。
输出格式
每次查询输出一行:若无合法方案,输出 -1;否则输出所求的 个事件编号,顺序必须为时间顺序,而非把编号重新排序。
数据范围
- 。
- 。
- 每个查询满足 。
- 所有查询的 之和不超过 ,包括不可行查询。
样例
输入:
1
6 5
11 13
1 8
6 9
0 5
14 17
4 16
6
2
3
1
4
输出:
-1
1 5
2 1 5
1
4 3 1 5
子任务
| 编号 | 附加限制 | 分值 |
|---|---|---|
| 1 | 11 | |
| 2 | 10 | |
| 3 | ||
| 4 | 13 | |
| 5 | 19 | |
| 6 | 所有事件持续时间相同 | 12 |
| 7 | 15 | |
| 8 | 无附加限制 | 10 |