#1481. 回文

回文

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定正整数 n\red n 和整数序列 a1,a2,,a2n\red {a_1,a_2,…,a_{2n}},在这 2n\red {2n} 个数中,1,2,,n\red {1,2,…,n} 分别各出现恰好 2\red 2 次。

现在进行 2n\red {2n} 次操作,目标是创建一个长度同样为 2n\red {2n} 的序列 b1,b2,,b2n\red {b_1,b_2,…,b_{2n}},初始时 b\red b 为空序列,每次可以进行以下两种操作之一:

  • 1. 将序列 a\red a 的开头元素加到 b\red b 的末尾,并从 a\red a 中移除。
  • 2. 将序列 a\red a 的末尾元素加到 b\red b 的末尾,并从 a\red a 中移除。

我们的目的是让 b\red b 成为一个 回文数列 ,即令其满足对所有 1in\red {1≤i≤n},有 bi=b2n+1i\red {b_i=b_{2n+1−i}}

请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在输出格式中说明。

输入格式

每个测试点包含多组测试数据。

输入的第一行,包含一个整数 T\red T,表示测试数据的组数。

对于每组测试数据:

第一行,包含一个正整数 n\red n

第二行,包含 2n\red {2n} 个用空格隔开的整数 a1,a2,,a2n\red {a_1,a_2,…,a_{2n}}

输出格式

对每组测试数据输出一行答案。

如果无法生成出回文数列,输出一行 ‐1,否则输出一行一个长度为 2n\red {2n} 的、由字符 LR 构成的字符串(不含空格),其中 L 表示移除开头元素的操作 1\red 1R 表示操作 2\red 2

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下:长度均为 2n\red {2n} 的字符串 s12n\red {s_{1∼2n}}t12n\red {t_{1∼2n}} 字典序小,当且仅当存在下标 1k2n\red {1≤k≤2n} 使得对于每个 1i<k\red {1≤i<k}si=ti\red {s_i=t_i}sk<tk\red {s_k<t_k}

输入输出样例

输入样例1

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

输出样例1

LRRLLRRRRL
-1

说明/提示

样例解释

在第一组数据中,生成的的 b\red b 数列是 [4,5,3,1,2,2,1,3,5,4]\red {[4,5,3,1,2,2,1,3,5,4]},可以看出这是一个回文数列。

另一种可能的操作方案是 LRRLLRRRRR,但比答案方案的字典序要大。

数据范围

n\red {∑n} 表示所有 T\red {T} 组测试数据中 n\red n 的和。

对所有测试点保证 1T1001n,n5×105\red {1≤T≤100,1≤n,∑n≤5×10^5}

测试点编号 T\red {T≤} n\red {n≤} n\red {∑n≤} 特殊性质
17\red {1∼7 } 10\red {10 } 10\red {10 } 50\red { 50 }
810\red {8∼10 } 100\red {100} 20\red {20 } 1000\red { 1000 }
1112\red {11∼12} 100\red {100 }
1315\red {13∼15} 1000\red {1000 } 25000\red { 25000}
1617\red {16∼17} 1\red {1 } 5×105\red {5×10^5} 5×105\red { 5×10^5}
1820\red {18∼20} 100\red {100}
2125\red {21∼25}

特殊性质:如果我们每次删除 a\red a 中两个相邻且相等的数,存在一种方式将序列删空(例如 a=[1,2,2,1]\red {a=[1,2,2,1]})。

2020年CSP-S第二轮重现

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-11 9:45
结束于
2023-10-19 17:45
持续时间
200 小时
主持人
参赛人数
15