[AdditionalFile5254.zip](file://AdditionalFile5254.zip?type=additional_file)

#5254. 「NOISG 2022 Final」Towers

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2022 Final T3. Towers

兔子本森喜欢塔楼。有 $N$ 个城市，编号从 $1$ 到 $N$，城市 $i$ 位于整数坐标点 $(X_i, Y_i)$。没有两个城市位于同一坐标点。本森希望在某些城市中建造塔楼，满足以下条件：

• 对于任意 $a$，$x$ 坐标为 $a$ 的塔楼最多有两座。
• 对于任意 $b$，$y$ 坐标为 $b$ 的塔楼最多有两座。
• $N$ 个城市中的每一个要么建有塔楼，要么位于具有相同 $x$ 坐标或相同 $y$ 坐标的两个塔楼之间的线段上。更正式地，对于位于 $(x, y)$ 的城市，如果该城市没有塔楼，则必须存在两个塔楼位于 $(x, c)$ 和 $(x, d)$，且 $c \leq y \leq d$，或者存在两个塔楼位于 $(e, y)$ 和 $(f, y)$，且 $e \leq x \leq f$。

本森知道总是可以建造满足这些条件的塔楼，但不知道如何实现。帮助本森确定应在哪些城市建造塔楼。

输入格式

程序需从标准输入读取数据。

第一行包含一个整数 $N$，表示城市数量。

接下来的 $N$ 行，第 $i$ 行包含两个整数 $X_i, Y_i$，表示城市 $i$ 位于坐标点 $(X_i, Y_i)$。

输出格式

程序需向标准输出输出结果。

输出一行，包含 $N$ 个字符的字符串 $A_1 A_2 \ldots A_N$。若本森应在城市 $i$ 建造塔楼，则 $A_i$ 为 1；否则为 0。建造的塔楼需满足所有条件。

如果有多种答案，程序可以输出任意一种。

样例 1

输入

3
1 1
1 6
1 5

输出

110

如果在城市 $1$ 和 $2$ 建造塔楼，它们具有相同的 $x$ 坐标，城市 $3$ 也具有相同的 $x$ 坐标，且位于它们之间的线段上。

错误的输出为 111，因为若在所有 $3$ 个城市都建造塔楼，$x$ 坐标为 $1$ 的塔楼将超过两座。

另一个错误的输出为 101，因为尽管城市 $2$ 与城市 $1$ 和 $3$ 具有相同的 $y$ 坐标，但它不在它们之间的线段上。

这个样例满足子任务 $1, 2, 5, 6, 7$ 的限制。

样例 2

输入

6
1 1
1 2
2 1
2 2
3 1
3 2

输出

110011

城市 $3$ 位于城市 $1$ 和 $5$ 之间的线段上，两者具有相同的 $y$ 坐标；城市 $4$ 位于城市 $2$ 和 $6$ 之间的线段上，两者具有相同的 $y$ 坐标。

这个样例满足子任务 $2, 5, 6, 7$ 的限制。

样例 3

输入

8
1 13
2 13
7 27
7 13
7 2
2 27
7 4
4 13

输出

10101101

这个样例满足子任务 $2, 5, 6, 7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^6$
• $1 \leq X_i, Y_i \leq 10^6$
• 对于所有 $i \neq j$，$X_i \neq X_j$ 或 $Y_i \neq Y_j$。

详细子任务附加限制及分值如下表所示：