Perils in Parallel

题目描述

在被 AlDebaran 王国入侵后，炸弹被安放在我国 AtCoder Kingdom 的各处。幸运的是，我们的军队团队 ABC 设法获得了一个属于控制这些炸弹系统的设备的一部分。共有 $N$ 个炸弹，编号为 $1$ 到 $N$，炸弹 $i$ 被安放在坐标 $A_i$。如果 $B_i=1$ 则表示它当前已激活，如果 $B_i=0$ 则表示已停用。该设备有 $M$ 根绳索，编号为 $1$ 到 $M$。如果我们切断绳索 $j$，所有植于坐标 $L_j$ 到 $R_j$（含端点）之间的炸弹的状态都会被切换——从激活变为停用，反之亦然。判断是否有可能使所有炸弹同时停用。如果答案是肯定的，输出应该切断的绳索集合。

输入格式

输入由标准输入按如下格式给出： $N$ $M$ $A_1$ $B_1$ $:$ $A_N$ $B_N$ $L_1$ $R_1$ $:$ $L_M$ $R_M$

输出格式

如果不可能使所有炸弹同时停用，输出 $-1$。如果可以，则输出应切断的绳索集合，格式如下： $k$ $c_1$ $c_2$ $\dots$ $c_k$

这里，$k$ 是绳索的数量（可以为 $0$），$c_1, c_2, \dots, c_k$ 表示应切断的绳索。必须满足 $1 \leq c_1 < c_2 < \dots < c_k \leq M$。

3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

2
1 4

4 2
2 0
3 1
5 1
7 0
1 4
4 7

-1

3 2
5 0
10 0
8 0
6 9
66 99

0

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

5
1 7 8 9 11

提示

输入中所有值均为整数。 $1 \leq N \leq 10^5$ $1 \leq A_i \leq 10^9\ (1 \leq i \leq N)$ $A_i$ 两两互不相同。 $B_i$ 为 $0$ 或 $1$。 $(1 \leq i \leq N)$ $1 \leq M \leq 2 \times 10^5$ $1 \leq L_j \leq R_j \leq 10^9\ (1 \leq j \leq M)$坐标为 $5, 10$ 的有两个已激活的炸弹，坐标为 $8$ 有一个已停用的炸弹。切断绳索 $1$ 会切换坐落在坐标 $1$ 到 $10$ 之间的所有炸弹的状态，也就是所有三个炸弹。切断绳索 $4$ 会切换坐落在坐标 $8$ 到 $9$ 之间的炸弹的状态，也就是炸弹 $3$。因此，我们可以通过切断绳索 $1$ 和绳索 $4$ 将所有炸弹停用。
切断任意集合的绳索都无法使所有炸弹同时停用。
所有炸弹已经停用，所以我们不需要切断任何绳索。
如果存在多个切断后可以使所有炸弹停用的绳索集合，任意一个都可以输出。

标签: AtCoder|abc155F

来源

AtCoder|abc155F