← 返回题目列表

AtCoder · awc0100_l

L. 日程调整

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

分数: 500 分

问题陈述

高桥正在管理学园祭的舞台表演日程。这里,我们只考虑每个演示的开始时间,而不考虑演示的持续时间。

有 N 主持人。主持人 i (1 \leq i \leq N) 有两个候选者的演示开始时间:要么从 时间开始 A_i 分钟,或精确延迟 D_i 时间开始分钟 A_i + D_i 分钟。

Takahashi 决定是否延迟每位演示者的演示。这个决定由一个字符串表示 S 长度 N 仅包含 0 和 1.

  • 当 S_i = 0,主持人 i 开始他们的演示时间 A_i 分钟。
  • 当 S_i = 1,主持人 i 开始他们的演示时间 A_i + D_i 分钟。

此外,我们还得到 M 一对演示者,其演示开始时间应尽可能相距较远,因为他们共享一些观众。的 j第对 (1 \leq j \leq M) 由演示者组成 U_j 和演示者 V_j.

对于字符串 S,我们定义 f(S) 如下:

  • 对于每对 j (1 \leq j \leq M),计算presenter实际开始时间的绝对差 U_j 和演示者的实际开始时间 V_j。这些绝对差异的最小值是 f(S).

高桥的目标是最大化 f(S)。让 K 是最大值 f(S)。找到以下内容:

  1. 的值 K
  2. 字典顺序最小的字符串 S 实现 f(S) = K.

这里,字符串的字典顺序比较是用 0 < 1.

约束

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 5000
  • N \times M \leq 10^6
  • 0 \leq A_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 1 \leq U_j, V_j \leq N
  • U_j \neq V_j
  • 所有对 (U_j, V_j) 都是唯一的,无论顺序如何。
  • 所有输入值均为整数。

输入

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

N M
A_1 D_1
A_2 D_2
\vdots
A_N D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

N 是演示者的数量,并且 M 是对的数量。 A_i 是演示者的预定开始时间(以分钟为单位) i,和 D_i 是演示者的延迟持续时间(以分钟为单位) i. U_j 和 V_j 是构成演示者的索引 j第对。

输出

按以下格式输出:

K
S

第一行,输出最大值 K of f(S)。第二行,输出字典序最小的字符串 S 实现 f(S) = K.


示例输入 1

3 2
10 5
12 10
30 3
1 2
2 3

示例输出 1

11
011

示例输入 2

4 4
0 10
10 5
18 2
25 10
1 2
2 3
3 4
1 4

示例输出 2

10
0011

示例输入 3

8 10
5 7
20 4
13 15
40 10
0 30
55 5
25 20
70 8
1 2
1 3
2 4
3 4
3 5
4 6
5 7
6 8
2 7
1 8

示例输出 3

12
00100010

示例输入 4

15 25
100 30
150 20
80 100
300 40
260 75
400 10
50 200
500 60
620 80
700 25
710 90
900 100
850 30
1000 150
1100 50
1 2
1 3
1 7
2 3
2 4
2 8
3 5
3 7
4 5
4 6
4 9
5 6
5 10
6 8
6 11
7 8
7 12
8 9
8 13
9 10
9 14
10 11
11 15
12 13
14 15

示例输出 4

40
110000100010000

示例输入 5

2 1
0 1000000000
1000000000 1000000000
1 2

示例输出 5

2000000000
01