← 返回题目列表

AtCoder · agc056_c

C. 01 平衡

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

分数: 900 点

问题陈述

考虑制作一个字符串 s 长度 N 组成 0 和 1,其中 s 必须满足 M 条件。 的 i-第条件用整数表示 L_i 和 R_i (1 \leq L_i < R_i \leq N)。 这意味着应该有相同数量的 0 和 1 之间 L_i-th 和 R_i第个字符(含) s.

查找字典顺序最小的字符串 s 满足所有条件。 可以证明问题的约束条件保证了 s 满足条件。

约束

  • 2 \leq N \leq 10^6
  • 1 \leq M \leq 200000
  • 1 \leq L_i < R_i \leq N
  • (R_i-L_i+1) \equiv 0 \mod 2
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印答案。


示例输入 1

4 2
1 2
3 4

示例输出 1

0101

示例输入 2

6 2
1 4
3 6

示例输出 2

001100

示例输入 3

20 10
6 17
2 3
14 19
5 14
10 15
7 20
10 19
3 20
6 9
7 12

示例输出 3

00100100101101001011