4177. 「CEOI2024」洒水器

题目描述

题目译自 CEOI 2024 Day2 T3「Sprinklers」

瓦茨拉夫有一个美丽的花园，花园里种了一排 $M$ 朵花。在这一排上，瓦茨拉夫还放置了 $N$ 个洒水器来浇花。

洒水器的位置由数字 $s_1, s_2, \ldots , s_N$ 给出。花的位置由数字 $f_1, f_2, \ldots , f_M$ 给出。两者都是非递减顺序，即：

• $s_1 \leq s_2 \leq \ldots \leq s_N$
• $f_1 \leq f_2 \leq \ldots \leq f_M$

瓦茨拉夫很快就要去参加 CEOI 了。他想确保在他离开期间所有的花都能得到适当的浇水。为此，他可以单独将每个洒水器向左或向右旋转，并设置它们的喷水强度——所有洒水器共享同一个水管，因此喷射距离相同。

如果喷水强度为 $K$，并且第 $i$ 个洒水器向左旋转，它将浇灌位置在 $[s_i - K, s_i]$ 之间的所有花。类似地，如果第 $j$ 个洒水器向右旋转，它将浇灌位置在 $[s_j, s_j+K]$ 之间的所有花。单个洒水器可以浇灌多朵花，一朵花也可以被多个洒水器浇灌。

你的任务是决定是否可以浇灌所有的花。如果是，你应该找到最小的足够喷水强度，以及相应的洒水器配置。如果存在多个具有最小喷水强度的有效配置，输出其中任何一个。

输入格式

输入的第一行包含两个用空格隔开的整数 $N$ 和 $M$。
第二行包含 $N$ 个空格分隔的整数 $s_1, s_2, \ldots , s_N$，表示洒水器的位置。
第三行包含 $M$ 个空格分隔的整数 $f_1, f_2, \ldots , f_M$，表示花的位置。

输出格式

如果无法浇灌所有的花，则输出数字 $-1$。

如果可以，输出应该包含两行。
第一行输出数字 $K$，表示浇灌所有花所需的最小的喷水强度。
在第二行，输出长度为 $N$ 的字符串 $c$，其中 $c_i$ 为 L，如果第 $i$ 个洒水器应该向左旋转，否则为 R。

---

样例 1

输入

3 3
10 10 10
5 11 16

输出

6
LLR

解释
每朵花至少被一个洒水器浇水。喷水强度低于 $6$ 是不可能的，因为位置 $16$ 的花离最近的洒水器有 $6$ 个单位距离。

---

样例 2

输入

1 2
1000
1 2000

输出

-1

解释
无论洒水器的方向如何，一次最多只能浇灌一朵花。

---

数据范围与提示

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

• $1 \leq N,M \leq 10^5$
• $0 \leq s_{i} \leq 10^9\ (1 \leq i \leq N)$
• $0 \leq f_{i} \leq 10^9\ (1 \leq i \leq M)$
• $s_{i} \leq s_{j}\ (i \leq j)$
• $f_{i} \leq f_{j}\ (i \leq j)$

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

子任务	附加限制	分值
1	$N = 1$	3
2	$N = 3x$，$x$ 是一个整数，$s_{3i+1}=s_{3i+2}=s_{3i+3}\ (0 \leq i \leq x-1)$（即洒水器总是成组放置三个）	6
3	$N \leq 10, M \leq 1\,000$	17
4	$K\leq 8$（即在所有测试数据中，存在一种洒水器配置，使得喷水强度最多为 $8$ 就足以浇灌所有的花）	27
5	无附加限制	47