#P6693. [2019山东省队集训第一轮]等你哈苏德

    ID: 6543 传统题 1000ms 512MiB 尝试: 12 已通过: 3 难度: 8 上传者: 标签>难度分类提高+/省选-模拟与实现技巧半开区间统一排序与序列处理离散化一维差分构造与建模奇偶性分析图论供需平衡建模Dinic当前弧优化CF2500

[2019山东省队集训第一轮]等你哈苏德

[2019山东省队集训第一轮]等你哈苏德[废题]

题目背景

当神树大人的落叶快把神 J 埋住时,他们仍在讨论时间回溯与宇宙能够解决的问题。神树大人提出可以把提出无法解决的问题的人丢出去。

神 J 回到小屋,拿出一个黑盒子,请神树大人运行。宇宙立刻弹出了 114514114514 个问题。神树大人不高兴地点了“把提出问题的人丢出去”,然后宇宙就毁灭了。

题目描述

数轴上有 mm 个闭区间 [Li,Ri][L_i,R_i],其中一些已被指定为黑色或白色,另一些尚未染色。

为所有未染色的区间选择颜色,已指定的颜色不能改变。要求对数轴上的每个整数点,覆盖它的黑色区间数量与白色区间数量之差的绝对值均不超过 11。

若存在方案,输出任意一种;否则输出 −1-1。

输入格式

第一行两个正整数 m,nm,n,注意区间数量 mm 在前。

接下来 mm 行,每行三个整数 Li,Ri,wiL_i,R_i,w_i:

  • wi=−1w_i=-1 表示未染色;
  • wi=0w_i=0 表示已指定为白色;
  • wi=1w_i=1 表示已指定为黑色。

所有区间均包含左右端点。覆盖差只检查整数坐标;例如原样例 2 在非整数位置 (4,5) 上不满足实数点模型,本题按整数点解释。

输出格式

若无解,输出一行 −1-1。

否则,输出一行 mm 个 0/10/1 整数,按输入顺序表示每个区间的颜色,00 为白色,11 为黑色。

样例输入 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≤n≤1091\le n\le10^9,1≤m≤3×1041\le m\le3\times10^4,1≤Li≤Ri≤n1\le L_i\le R_i\le n,wi∈{−1,0,1}w_i\in\{-1,0,1\}。

子任务 分值 nn 的上界 mm 的上界 特殊性质
1 25 分 2020 3×1043\times10^4 所有 wi=−1w_i=-1
2 15 分 10910^9 2020 无
3 20 分 3×1043\times10^4 所有 wi=−1w_i=-1
4 40 分 无

本题使用构造检查器,任意合法着色均可通过;无解输出 -1。