对着题解写 写挂 16pts WA
查看原帖
对着题解写 写挂 16pts WA
817524
CR400BFAZ5254楼主2024/9/3 21:50
#include<bits/stdc++.h>
#define MAXN 1000010
using namespace std;
int a[MAXN],n;
char ans[MAXN],cur[MAXN];
//手写栈
struct sta{
    int st[MAXN],l,r;
    int left(){return st[l];}
    int right(){return st[r];}
    void push(int x){st[r++]=x;}
    void popleft(){l++;}
    void popright(){r--;}
    void clear(){l=r=0;}
    bool empty(){return l==r;}
    int size(){return r-l;}
}ll,rr;
int pos(int l,int r,int val){
    for(int i=l;i<=r;i++){
        if(a[i]==val) return i;
    }
    return -1;
}
void init(){
    int now=2;
    while(true){
        if(ll.empty()&&rr.empty()) break;
        else if(rr.empty()){
            if(ll.left()!=ll.right()){
                cur[1]='Z';
                return ;
            }
            cur[now]=cur[2*n-now+1]='L';
            ll.popleft();
            ll.popright();
        }else if(ll.empty()){
            if(rr.left()!=rr.right()){
                cur[1]='Z';
                return ;
            }
            cur[now]=cur[2*n-now+1]='R';
            rr.popleft();
            rr.popright();
        }else{
            if(ll.right()==ll.left()&&ll.size()>1){
                cur[now]=cur[2*n-now+1]='L';
                ll.popleft();
                ll.popright();
            }else if(ll.right()==rr.left()){
                cur[now]='L';
                cur[2*n-now+1]='R';
                rr.popleft();
                ll.popright();
            }else if(ll.left()==rr.right()){
                cur[now]='R';
                cur[2*n-now+1]='L';
                rr.popright();
                ll.popleft();
            }else if(rr.left()==rr.right()&&rr.size()>1){
                cur[now]='R';
                cur[2*n-now+1]='R';
                rr.popleft();rr.popright();
            }else{
                cur[1]='Z';
                return ;
            }
        }
        now++;
    }
}
bool check(){
    int x=1;
    while(x<=2*n&&cur[x]==ans[x]) x++;
    return x<=2*n&&cur[x]<ans[x];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int p;
        ans[1]='Y';
        cin >> n;
        for(int i=1;i<=n*2;i++){
            cin >> a[i];
        }
        ll.clear();
        rr.clear();
        p=pos(2,2*n,a[1]);
        // get into the stack
        for(int i=p-1;i>=2;i--) ll.push(a[i]);
        for(int i=p+1;i<=2*n;i++) rr.push(a[i]);
        cur[1]='L',cur[2*n]='L';
        init();
        
        if(check()){
            for(int i=1;i<=2*n;i++) ans[i]=cur[i];
        }

        ll.clear();
        rr.clear();
        p=pos(1,2*n-1,a[2*n]);
        // get into the stack
        for(int i=p-1;i>=1;i--) ll.push(a[i]);
        for(int i=p+1;i<=2*n-1;i++) rr.push(a[i]);
        cur[1]='R',cur[2*n]='L';
        init();
        
        if(check()){
            for(int i=1;i<=2*n;i++) ans[i]=cur[i];
        }
        if(ans[1]=='Y'){
            cout << -1 << endl;
        }else{
            for(int i=1;i<=2*n;i++) cout << ans[i];
            cout << endl;
        }
    }



    return 0;
}
2024/9/3 21:50
加载中...