bzoj#P2811. [APIO2012] Guard
[APIO2012] Guard
题目描述
APIO 王国正被忍者攻击!忍者非常厉害,因为他们在进攻的时候可以躲在 阴影里面使得其他人看不到他们。整个王国除了国王居住的 APIO 城堡以外都已 经被占领了。在城堡前,有 个灌木丛,从 到 编号,有 个忍者躲在恰好 个灌木丛后面。APIO 城堡里有 个守卫。守卫 监视着编号从 到 的连续的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为国王的仆人,你需要告诉国王,基于守卫的报告,哪些灌木丛后面一定躲着一个忍者,即对于任何和守卫报告不矛盾的忍者排列方式,在这个灌木丛后面都躲着一个忍者。
你需要写一个程序来输出所有的这些灌木丛的编号。
输入格式
第一行包含三个用空格分隔的整数 , 是灌木丛的个数, 是忍者的个数, 是守卫的个数。
接下来 行,每行描述一个守卫的信息。其中的第 行包含三个整数 ,表示第 个守卫的监视范围是从 到 ()。 是 或者 ,若是 表示范围内没有看到忍者, 表示范围内有至少一个忍者。
输入数据保证至少存在一种忍者排列方式满足所有条件。
输出格式
若存在灌木丛,在其后面一定躲着忍者,则将这些一定躲着忍者的灌木丛按 照编号从小到大的顺序依次输出,每个一行。即若有 个这样的灌木丛,则需要输出 行。若不存在,则输出一行一个 -1
,不包含引号。
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
3
5
样例 1 解释
在这个样例中,有两种可能的安排方式: 或者 。即 和 后面必然躲着一个忍者。考虑第一个灌木丛,存在一种安排方案使得它的后面躲着忍者,但也存在一种安排方案使得它后面没有躲忍者,因此不应该输出 。同理,不应该输出 。
5 1 1
1 5 1
-1
样例 2 解释
在这个样例中,没有灌木丛后面一定躲着忍者。
数据范围
对于 的数据,,。
对于 的数据,,。
对于所有数据,保证灌木的数量 ,忍者数 ,守卫数 。