24pts求调
查看原帖
24pts求调
905636
_xguagua_Firefly_楼主2024/10/7 19:02
#include <bits/stdc++.h>
#define int long long
#define len(s) (int)s.size()
using namespace std;

const int MAXN = 5e5 + 24;
int T;
int n,x1,x2;
int a[2 * MAXN];
bool ans[2 * MAXN];//0:L 1:R
deque<int> p,q;
bool solve()
{
    int l = 2,r = 2 * n - 1;
    while(l < r)
    {
        if(len(p) > 1 && p.front() == p.back())
        {
            ans[l] = ans[r] = 0;
            l++,r--;
            p.pop_back(),p.pop_front();
        }
        else if(!p.empty() && !q.empty() && p.front() == q.back())
        {
            ans[l] = 0,ans[r] = 1;
            l++,r--;
            p.pop_front(),q.pop_back();
        }
        else if(len(q) > 1 && q.front() == q.back())
        {
            ans[l] = ans[r] = 1;
            l++,r--;
            q.pop_back(),q.pop_front();
        }
        else if(!p.empty() && !q.empty() && q.front() == p.back())
        {
            ans[l] = 1,ans[r] = 0;
            l++,r--;
            q.pop_front(),p.pop_back();
        }
        else {return 0;}
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1;i <= 2 * n;i++)
            cin >> a[i];
        for(int i = 1;i <= 2 * n;i++)
        {
            if(a[i] == a[1] && i != 1)
                x1 = i;
            if(a[i] == a[2 * n] && i != 2 * n)
                x2 = i;
        }
        ans[1] = ans[2 * n] = 0;
        for(int i = 2;i < x1;i++)
            p.push_back(a[i]);
        for(int i = 2 * n ;i > x1;i--)
            q.push_back(a[i]);
        if(solve())
        {
            for(int i = 1;i <= 2 * n;i++)
                cout << ((ans[i]) ? 'R' : 'L');
            cout << "\n";
            continue;
        }
        p.clear(),q.clear();
        ans[1] = 1;
        for(int i = 1;i < x2;i++)
            p.push_back(a[i]);
        for(int i = 2 * n - 1;i > x2;i--)
            q.push_back(a[i]);
        if(solve())
        {
            for(int i = 1;i <= 2 * n;i++)
                cout << ((ans[i]) ? 'R' : 'L');
            cout << "\n";
            continue;
        }
        else
        {cout << "-1\n";}
    }
}
2024/10/7 19:02
加载中...