#P15807. [中国国家队2025年林芝集训]孑孓王可

    ID: 15018 传统题 1500ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>算法基础二分贪心数据结构线段树构造模拟CF3000

[中国国家队2025年林芝集训]孑孓王可

题目描述

有一个无限长的数列 AA,初始时所有元素均为 00。

给定 nn 个区间 [li,ri][l_i,r_i]。对于每个 i=1,2,…,ni=1,2,\ldots,n,你需要恰好选择以下两种操作之一执行:

  1. 对所有 j∈[li,ri]j\in [l_i,r_i],令 Aj←Aj+1A_j\gets A_j+1;
  2. 对所有 j∈Zj\in\mathbb Z 且 j∉[li,ri]j\notin [l_i,r_i],令 Aj←Aj+1A_j\gets A_j+1。

请构造一组选择方案,使得所有操作完成后,数列 AA 中的最大值尽可能小。

输入格式

第一行包含一个正整数 nn。

接下来 nn 行,第 ii 行包含两个正整数 li,ril_i,r_i。

输出格式

第一行输出一个正整数,表示可以达到的最小最大值。

第二行输出一个长度为 nn 的 01 串 ss:

  • si=0s_i=\texttt{0} 表示第 ii 个区间选择操作 2;
  • si=1s_i=\texttt{1} 表示第 ii 个区间选择操作 1。

样例

输入

5
10 10
6 6
1 7
2 5
2 7

输出

2
11110

解释

另一种合法输出为:

2
11011

数据范围

对于 100%100\% 的数据,保证:

  • 1≤n≤2×1051\le n\le 2\times 10^5;
  • 1≤li≤ri≤2n1\le l_i\le r_i\le 2n。

子任务

子任务编号 n≤n\le 分值
1 20 7
2 150 24
3 10310^3 21
4 5×1045\times 10^4 34
5 2×1052\times 10^5 14