蒟蒻刚学 OI 1s,20pts 求助
查看原帖
蒟蒻刚学 OI 1s,20pts 求助
178195
人间温柔楼主2022/9/4 21:29
#include<bits/stdc++.h>
using namespace std;

const int maxn=500005;
const int maxn2=maxn*2;

int n,n2;
int same_to1,same_ton2;
int a[maxn2];
int L[maxn2],R[maxn2],headL,headR,tailL,tailR;
int LL[maxn2],RR[maxn2];

char ans[maxn2],tmp[maxn2];
int k;

bool first_L(){
	ans[1]='L';
	k=1;
	headL=headR=0;
	tailL=tailR=1;
	for(int i=same_to1-1;i>=2;i--){
		L[++headL]=a[i];
	}
	for(int i=same_to1+1;i<=n2;i++){
		R[++headR]=a[i];
	}
	while(headL>=tailL || headR>=tailR){

		if(L[headL]==L[tailL] && headL!=tailL){
			ans[++k]='L';
			tmp[k]='L';
			headL--;
			tailL++;
		}
		else if(L[headL]==R[tailR]){
			ans[++k]='L';
			tmp[k]='R';
			headL--;
			tailR++;
		}
		else if(R[headR]==L[tailL]){
			ans[++k]='R';
			tmp[k]='L';
			headR--;
			tailL++;
		}
		else if(R[headR]==R[tailR] && headR!=tailR){
			ans[++k]='R';
			tmp[k]='R';
			headR--;
			tailR++;
		}
		else return false;
	}
	return true;
}

bool first_R(){
	ans[1]='R';
	k=1;
	headL=headR=0;
	tailL=tailR=1;
	for(int i=same_ton2-1;i>=1;i--){
		LL[++headL]=a[i];
	}
	for(int i=same_ton2+1;i<n2;i++){
		RR[++headR]=a[i];
	}
	
	while(headL>=tailL || headR>=tailR){
		if(LL[headL]==LL[tailL] && headL!=tailL){
			ans[++k]='L';
			tmp[k]='L';
			headL--;
			tailL++;
		}
		else if(LL[headL]==RR[tailR]){
			ans[++k]='L';
			tmp[k]='R';
			headL--;
			tailR++;
		}
		else if(RR[headR]==LL[tailL]){
			ans[++k]='R';
			tmp[k]='L';
			headR--;
			tailL++;
		}
		else if(RR[headR]==RR[tailR] && headR!=tailR){
			ans[++k]='R';
			tmp[k]='R';
			headR--;
			tailR++;
		}
		else return false;
	}
	return true;
}

void work(){
	cin>>n;
	n2=n*2;
	for(int i=1;i<=n2;i++){
		cin>>a[i];
		if(i!=1 && a[i]==a[1]){
			same_to1=i;
		}
	}
	for(int i=n2-1;i>=1;i--){
		if(a[i]==a[n2]){
			same_ton2=i;
			break;
		}
	}
	
	if(first_L()==true){
		for(int i=1;i<=k;i++){
			cout<<ans[i];
		}
		for(int i=k;i>=2;i--){
			cout<<tmp[i];
		}
		cout<<'L'<<endl;
	}
	else if(first_R()==true){
		for(int i=1;i<=k;i++){
			cout<<ans[i];
		}
		for(int i=2;i<=k;i++){
			cout<<tmp[i];
		}
		cout<<'L'<<endl;
	}
	else cout<<"-1"<<endl;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		memset(L,0,sizeof(L));
		memset(R,0,sizeof(R));
		memset(LL,0,sizeof(LL));
		memset(RR,0,sizeof(RR));
		work();
	}
	return 0;
}
2022/9/4 21:29
加载中...