96pts TLE求调 #17跑了 30s
查看原帖
96pts TLE求调 #17跑了 30s
907113
c_y_z楼主2024/10/23 08:20
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int t,n,a[N*2];
int q1[N*2],q2[N*2];
int back1,front1,back2,front2;
bool flag;
string ans1,ans2;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void solve(bool f1,bool f2){
	if(f1){ans1=ans1+'L';front1++;}
	else {ans1=ans1+'R';front2++;}
	if(f2){ans2='L'+ans2;back1--;}
	else{ans2='R'+ans2;back2--;}
}
inline void init(){
	back1=back2=0;
	front1=front2=1;
}
inline void work(int op){
	int x;
	if(op==1){
		for(int i=2;i<=n*2;i++) if(a[i]==a[1]){x=i;break;}
		for(int i=1;i<=x;i++) q1[++back1]=a[i];
		for(int i=n*2;i>x;i--) q2[++back2]=a[i];
	}else{
		for(int i=1;i<n*2;i++) if(a[i]==a[n*2]){x=i;break;}
		for(int i=1;i<x;i++) q1[++back1]=a[i];
		for(int i=n*2;i>=x;i--) q2[++back2]=a[i];
	}
	while(front1<=back1||front2<=back2){
		if(front1>back1){
			while(front2<=back2){
				if(q2[front2]!=q2[back2]){flag=0;break;}
				solve(0,0);
			}return;
		}
		if(front2>back2){
			while(front1<=back1){
				if(q1[front1]!=q1[back1]){flag=0;break;}
				solve(1,1);
			}return;
		}
		int a=q1[front1],b=q2[front2],c=q1[back1],d=q2[back2];
		if(front1==back1&&front2==back2){
			if(a==d) solve(1,0);
			else{flag=0;break;}
		}else if(front1==back1){
			if(a==d) solve(1,0);
			else if(c==b) solve(0,1);
			else if(b==d) solve(0,0);
			else{flag=0;break;}
		}else if(front2==back2){
			if(a==c) solve(1,1);
			else if(a==b) solve(1,0);
			else if(b==c) solve(0,1);
			else{flag=0;break;}
		}else{
			if(a==c) solve(1,1);
			else if(a==d) solve(1,0);
			else if(b==c) solve(0,1);
			else if(b==d) solve(0,0);
			else {flag=0;return;}
		}
	}
}
int main(){
	t=read();
	while(t--){
		n=read();
		for(int i=1;i<=n*2;i++) a[i]=read();
		init();
		ans1=ans2="";
		flag=1;
		work(1);
		if(flag){cout<<ans1<<ans2<<"\n";continue;}
		init();
		ans1=ans2="";
		flag=1;
		work(0);
		if(ans2[ans2.size()-1]=='R') ans2[ans2.size()-1]='L';
		if(flag){cout<<ans1<<ans2<<"\n";continue;}
		else cout<<"-1\n";
	}
	return 0;
} 
2024/10/23 08:20
加载中...