在LOJ上AC了,但是在洛谷却只有88pts?RE#16~18
查看原帖
在LOJ上AC了,但是在洛谷却只有88pts?RE#16~18
305891
Eraine楼主2021/11/15 11:42
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,num[500005],L[500005],R[500005],a[1000005];
char ans[1000005];
bool SolveL(){
	ans[1]='L';
	ans[2*n]='L';
	int wl=R[a[1]],wr=R[a[1]],l=2,r=2*n,front=1;
	while(wl+n-1>wr){
		if(a[wl-1]==a[l]&&l<wl-1){
			ans[2*n-front]='L';
			ans[++front]='L';
			l++;
			wl--;
		}else if(a[wr+1]==a[l]&&l<wl&&r>wr){
			ans[2*n-front]='R';
			ans[++front]='L';
			l++;
			wr++;
		}else if(a[wl-1]==a[r]&&l<wl&&r>wr){
			ans[2*n-front]='L';
			ans[++front]='R';
			r--;
			wl--;
		}else if(a[wr+1]==a[r]&&r>wr+1){
			ans[2*n-front]='R';
			ans[++front]='R';
			r--;
			wr++;
		}else
			return false;
	}
	return true;
}
bool SolveR(){
	ans[1]='R';
	ans[2*n]='L';
	int wl=L[a[2*n]],wr=L[a[2*n]],l=1,r=2*n-1,front=1;
	while(wl+n-1>wr){
		if(a[wl-1]==a[l]&&l<wl-1){
			ans[2*n-front]='L';
			ans[++front]='L';
			l++;
			wl--;
		}else if(a[wr+1]==a[l]&&l<wl&&r>wr){
			ans[2*n-front]='R';
			ans[++front]='L';
			l++;
			wr++;
		}else if(a[wl-1]==a[r]&&l<wl&&r>wr){
			ans[2*n-front]='L';
			ans[++front]='R';
			r--;
			wl--;
		}else if(a[wr+1]==a[r]&&r>wr+1){
			ans[2*n-front]='R';
			ans[++front]='R';
			r--;
			wr++;
		}else
			return false;
	}
	return true;
}
void Print(){
	for(int i=1;i<=2*n;i++)
		printf("%c",ans[i]);
	printf("\n");
}
void Work(){
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
		num[i]=0;
	for(int i=1;i<=2*n;i++){
		scanf("%d",&a[i]);
		if(num[a[i]]>0)
			R[a[i]]=i;
		else
			L[a[i]]=i,num[a[i]]=1;
	}
	if(SolveL())
		Print();
	else if(SolveR())
		Print();
	else
		printf("-1\n");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)
		Work();
	return 0;
}
2021/11/15 11:42
加载中...