记录编号	575484	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2021S]回文	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.066 s
提交时间	2022-09-16 21:32:15	内存使用	7.31 MiB

#include <bits/stdc++.h>
 
const int N = 1e6+10;
char res[N];
int n, cnt, a[N];
int q1[N], q2[N], h1, h2, t1, t2;
 
bool solve(char fst) {
    h1 = h2 = 0, t1 = t2 = 1, cnt = 2, res[1] = fst, res[n] = 'L';
    for (int i = 1; i <= n; ++ i) 
        if ((fst == 'L' && a[i] == a[1] && i != 1) || (fst == 'R' && a[i] == a[n] && i != n)) {
            for (int j = i - 1; j > 1 || (j == 1 && fst == 'R'); -- j) 
                q1[++ h1] = a[j];
            for (int j = i + 1; j < n || (j == n && fst == 'L'); ++ j) 
                q2[++ h2] = a[j];
        }
    while (h1 >= t1 || h2 >= t2) {
        if (h1 == t1 && h2 == t2 && q1[h1] == q2[h2]) {
            res[cnt] = 'L', res[cnt + 1] = 'R';
            break;
        } else if ((h1 > t1 && (q1[h1] == q1[t1] || (h2 >= t2 && q1[h1] == q2[t2]))) || (h1 == t1 && q1[h1] == q2[t2])) {
            if (h1 > t1 && q1[h1] == q1[t1]) res[n - cnt + 1] = 'L', ++ t1;
            else res[n - cnt + 1] = 'R', ++ t2;
            -- h1, res[cnt ++] = 'L';
        } else if ((h2 > t2 && (q2[h2] == q2[t2] || (h1 >= t1 && q2[h2] == q1[t1]))) || (h2 == t2 && q2[h2] == q1[t1])) {
            if (h2 > t2 && q2[h2] == q2[t2]) res[n - cnt + 1] = 'R', ++ t2;
            else res[n - cnt + 1] = 'L', ++ t1;
            -- h2, res[cnt ++] = 'R';
        } else return false;
    }
    for (int i = 1; i <= n; ++ i) 
        std::cout << res[i];
    std::cout << '\n';
    return true;
}
 
int main() {
    freopen("2021palin.in", "r", stdin); 
    freopen("2021palin.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t --) {
        std::cin >> n, n += n;
        for (int i = 1; i <= n; ++ i)
            std::cin >> a[i];
        if (!solve('L') && !solve('R')) 
            std::cout << "-1" << '\n';
    }
    return 0;
}