#P6693. [2019山东省队集训第一轮]等你哈苏德
[2019山东省队集训第一轮]等你哈苏德
[2019山东省队集训第一轮]等你哈苏德[废题]
题目背景
当神树大人的落叶快把神 J 埋住时,他们仍在讨论时间回溯与宇宙能够解决的问题。神树大人提出可以把提出无法解决的问题的人丢出去。
神 J 回到小屋,拿出一个黑盒子,请神树大人运行。宇宙立刻弹出了 个问题。神树大人不高兴地点了“把提出问题的人丢出去”,然后宇宙就毁灭了。
题目描述
数轴上有 个闭区间 ,其中一些已被指定为黑色或白色,另一些尚未染色。
为所有未染色的区间选择颜色,已指定的颜色不能改变。要求对数轴上的每个整数点,覆盖它的黑色区间数量与白色区间数量之差的绝对值均不超过 。
若存在方案,输出任意一种;否则输出 。
输入格式
第一行两个正整数 ,注意区间数量 在前。
接下来 行,每行三个整数 :
- 表示未染色;
- 表示已指定为白色;
- 表示已指定为黑色。
所有区间均包含左右端点。覆盖差只检查整数坐标;例如原样例 2 在非整数位置 (4,5) 上不满足实数点模型,本题按整数点解释。
输出格式
若无解,输出一行 。
否则,输出一行 个 整数,按输入顺序表示每个区间的颜色, 为白色, 为黑色。
样例输入 1
4 1000000000
1 9 -1
2 6 -1
1 8 -1
1 7 -1
样例输出 1
1 1 0 0
样例输入 2
5 1000000000
1 4 -1
2 8 0
5 7 -1
1 4 1
1 5 -1
样例输出 2
1 0 1 1 0
样例输入 3
4 1000000000
1 2 -1
1 2 1
1 2 1
2 3 1
样例输出 3
-1
数据范围
所有数据满足 ,,,。
| 子任务 | 分值 | 的上界 | 的上界 | 特殊性质 |
|---|---|---|---|---|
| 1 | 25 分 | 所有 | ||
| 2 | 15 分 | 无 | ||
| 3 | 20 分 | 所有 | ||
| 4 | 40 分 | 无 |
本题使用构造检查器,任意合法着色均可通过;无解输出 -1。