题目描述

题目译自 Romanian Master of Informatics 2024 Day1 T1 「Choose Interval」

你面临一个无限长的数组，数组中的每个位置最初都是 $0$，位置由整数编号标记。现在给你 $N$ 个区间，形式为 $[A, B]$，对于每个区间，你需要选择以下两种操作之一来处理这个数组：

• 翻转操作：将数组中除了位置 $A$ 到位置 $B$ 区间之外的所有值加 $1$。
• 常规操作：将数组从位置 $A$ 到位置 $B$ 区间内的所有值加 $1$。

你的任务是为每个区间选择一种操作方式，使得所有操作完成后，数组中的最大值尽可能小。

输入格式

输入的第一行是一个整数 $N$，表示区间的数量。接下来的 $N$ 行，每行包含两个空格分隔的整数 $A$ 和 $B$，表示一个区间的起点和终点。

输出格式

输出的第一行是一个整数，表示在最优选择下执行 $N$ 次操作后数组中的最大值。

第二行是一个长度为 $N$ 的二进制字符串，第 $i$ 个字符为 $0$ 表示第 $i$ 次操作选择了翻转操作，为 $1$ 表示选择了常规操作。

如果存在多种最优操作方案，输出任意一种有效方案即可。

5
10 10
6 6
1 7
2 5
2 7

2
11110

另一种同样合法的答案是：

2
11011

数据范围与提示

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

• $1 \leq N \leq 200 \ 000$
• $1 \leq A \leq B \leq 2 N$

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