← 返回题目列表

Codeforces · 1980/F1

F1. 现场划分(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本;它与硬版本的区别仅在于问题。简单版本只需要您打印某些值是否非零。硬版本需要您打印精确的值。

Alice 和 Bob 正在划分场地。该字段是一个大小为 $$$n \times m$$$ ($$$2 \le n, m \le 10^9$$$) 的矩形,行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。行 $$$r$$$ 和列 $$$c$$$ 交叉处的单元格表示为 ($$$r, c$$$)。

Bob 有 $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) 个喷泉,它们全部位于场地的不同单元格中。 Alice负责划分领域,但她必须满足几个条件:

- 为了划分场地,爱丽丝将在场地左侧或顶部的任何空闲(没有喷泉)单元格中开始她的路径,并移动,每次移动到向下或右侧的相邻单元格。她的路径将在场地的右侧或底部结束。
- Alice 的路径会将字段分为两部分 - 一部分属于 Alice(这部分包括她路径的单元格),另一部分属于 Bob。
- Alice 将拥有包含该单元的部分 ($$$n, 1$$$)。
- Bob 将拥有包含该单元的部分 ($$$1, m$$$)。

Alice 想要以获取尽可能多的单元格的方式划分字段。

鲍勃想要保留所有喷泉的所有权,但他可以将其中之一交给爱丽丝。首先,输出整数 $$$\alpha$$$ — 如果鲍勃没有给她任何喷泉(即所有喷泉都将保留在鲍勃的地块上),则爱丽丝地块的最大可能大小。然后输出 $$$k$$$ 非负整数 $$$a_1, a_2, \dots, a_k$$$,其中:

- $$$a_i=0$$$,如果 Bob 给 Alice 第 $$$i$$$ 个喷泉后,Alice 地块的最大可能大小不会增加(即保持等于 $$$\alpha$$$);
- $$$a_i=1$$$,如果 Bob 给 Alice 第 $$$i$$$ 个喷泉后,Alice 地块的最大可能大小会增加(即变得大于 $$$\alpha$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n, m \le 10^9$$$, $$$2 \le k \le 2 \cdot 10^5$$$)——分别是场大小和喷泉数量。

然后沿着 $$$k$$$ 行,每行包含两个数字 $$$r_i$$$ 和 $$$c_i$$$ ($$$1 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) — 具有第 $$$i$$$ 个喷泉的单元格的坐标。保证所有单元格都是不同的,并且没有一个单元格是 ($$$n, 1$$$)。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,首先输出 $$$\alpha$$$ — 如果 Bob 没有给 Alice 任何喷泉,则可以属于 Alice 的地块的最大大小。然后输出 $$$k$$$ 非负整数 $$$a_1, a_2, \dots, a_k$$$,其中:

- $$$a_i=0$$$,如果Bob给Alice第$$$i$$$个喷泉后,与所有$$$k$$$喷泉都属于Bob的情况相比,Alice的地块的最大可能大小不会增加;
- $$$a_i=1$$$,如果 Bob 给 Alice 第 $$$i$$$ 个喷泉后,与所有 $$$k$$$ 喷泉都属于 Bob 的情况相比,Alice 地块的最大可能大小会增加。

如果输出任何其他正数而不是适合 64 位有符号整数类型的 $$$1$$$,它也将被识别为 $$$1$$$。因此,该问题的困难版本的解决方案也将通过简单版本的测试。

示例

输入 #1

5
2 2 3
1 1
1 2
2 2
5 5 4
1 2
2 2
3 4
4 3
2 5 9
1 2
1 5
1 1
2 2
2 4
2 5
1 4
2 3
1 3
6 4 4
6 2
1 3
1 4
1 2
3 4 5
2 1
3 2
1 4
1 3
2 4

输出 #1

1
1 0 1 
11
0 1 0 1 
1
0 0 1 1 0 0 0 0 0 
6
1 0 0 0 
1
1 1 0 0 0

注意

下面是第二个示例的图像:

喷泉的索引标记为绿色。属于爱丽丝的细胞被标记为蓝色。

请注意,如果鲍勃给爱丽丝喷泉 $$$1$$$ 或喷泉 $$$3$$$,那么该喷泉不能在爱丽丝的地块上。