52pts求调(玄关)
查看原帖
52pts求调(玄关)
700558
williamwei楼主2024/10/16 19:48
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int t, n, p1, p2, h1, t1, h2, t2, a[maxn], s1[maxn], s2[maxn];
char res[maxn];
void move(int l, int r, int* ch, int& t) {for (int i = l; i <= r; i++) ch[t++] = a[i];}
bool solve(int p, bool st) {
    h1 = t1 = h2 = t2 = 0; res[n] = 'L'; res[1] = st ? 'R' : 'L';
    if (st) move(1, p - 1, s1, t1), reverse(s1, s1 + t1), move(p + 1, n - 1, s2, t2);
    else move(2, p - 1, s1, t1), reverse(s1, s1 + t1), move(p + 1, n, s2, t2);
    for (int cur = 2; h1 < t1 || h2 < t2; cur++)
        if (h1 < t1 - 1 && s1[h1] == s1[t1 - 1]) ++h1, --t1, res[cur] = res[n - cur + 1] = 'L';
        else if (h1 < t1 && h2 < t2 && s1[t1 - 1] == s2[h2]) --t1, ++h2, res[cur] = 'L', res[n - cur + 1] = 'R';
        else if (h1 < t1 && h2 < t2 && s1[h1] == s2[t2 - 1]) ++h1, --t2, res[cur] = 'R', res[n - cur + 1] = 'L';
        else if (h2 < t2 - 1 && s2[h2] == s2[t2 - 1]) ++h2, --t2, res[cur] = res[n - cur + 1] = 'R';
        else return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n; n <<= 1;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 2; i < n; i++)
            if (a[i] == a[1]) p1 = i;
            else if (a[i] == a[n]) p2 = i;
        if (!solve(p1, 0) && !solve(p2, 1)) cout << -1 << '\n';
        else cout << res + 1 << '\n';
    }
    return 0;
}
2024/10/16 19:48
加载中...