分数: 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)。找到以下内容:
- 的值 K
- 字典顺序最小的字符串 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