4596 - NOIP CSP 2021 提高: 第三题 回文(palin)

通过次数

2

提交次数

8

时间限制 : 1 秒
内存限制 : 512 MB

给定正整数 n 和整数序列 a1, a2, . . . , a2n,在这 2n 个数中,1, 2, . . . , n 分别各出现 恰好 2 次。现在进行 2n 次操作,目标是创建一个长度同样为 2n 的序列 b1, b2, . . . , b2n, 初始时 b 为空序列,每次可以进行以下两种操作之一:

  1. 将序列 a 的开头元素加到 b 的末尾,并从 a 中移除
  2. 将序列 a 的末尾元素加到 b 的末尾,并从 a 中移除 我们的目的是让 b 成为一个 .回 .文 .数 .列,即令其满足对所有 1 ≤ i ≤ n,有 bi = b2n+1−i。 请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

输入

每个测试点包含多组测试数据。 输入的第一行包含一个整数 T,表示测试数据的组数。 每组测试数据的第一行包含一个正整数 n,第二行包含 2n 个用空格隔开的整数a1, a2, . . . , a2n。

输出

对每个测试数据输出一行答案。 如果无法生成出回文数列,输出一行 ‐1,否则输出一行一个长度为 2n 的、由字符L 或 R 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1,R 表示操作 2。 你需要输出所有方案对应的字符串中字典序最小的一个。 字典序的比较规则如下:长度均为 2n 的字符串 s1..2n 比 t1..2n 字典序小,当且仅当存在下标 1 ≤ k ≤ 2n 使得 ∀1 ≤ i < k 有 si = ti 且 sk < tk。

样例

输入
复制

2
5
4 1 2 4 5 3 1 2 3 5
3 
3 2 1 2 1 3

输出
复制

LRRLLRRRRL
‐1

输入
复制

5
10
3 5 9 8 10 6 1 4 7 2 2 7 4 1 6 10 8 9 5 3
10
10 5 8 9 7 3 8 4 10 6 5 2 9 7 3 2 1 1 4 6
10
4 9 3 10 10 1 4 2 7 6 8 5 9 3 1 5 8 6 7 2
10
2 5 6 7 4 9 1 8 4 7 3 6 10 5 2 9 3 10 8 1
10
1 2 6 4 10 10 4 5 8 2 3 1 6 9 7 7 9 5 8 3

输出
复制

LLLLLLLLLLLLLLLLLLLL
-1
LRRRRRLLRLLLRRRRRRRL
-1
LRLLRRLLRRRRLLLLRLLL

提示

【样例 1 解释】 在第一组数据中,生成的的 b 数列是 4 5 3 1 2 2 1 3 5 4,可以看出这是一个回文数列。 另一种可能的操作方案是 LRRLLRRRRR,但比答案方案的字典序要大