WA了#17#26,求助。。。
查看原帖
WA了#17#26,求助。。。
297361
LiYueLin06楼主2021/11/8 21:19

(下不了数据好离谱)

#include<iostream>
#include<stdio.h>
using namespace std;
const int N=5e5+5;
int n,a[N],ans[N],pos[N],to[N];//ans[i]=j表示第i个删掉的数在原数组的位置是j 
int find(int st,int ed)
{
	int i,j,p=ed,q=ed,k;
	if(st==1)
	{
		i=2,j=2*n;
	}
	else
	{
		i=1,j=2*n-1;
	}
	for(k=2;k<=n;k++)
	{
		if(a[i]==a[p-1]&&i<p-1) 
		{
			ans[k]=i;
			ans[2*n+1-k]=p-1;		
			//cout<<"a "<<i<<" "<<j<<" "<<p-1<<" "<<q<<endl; 		
			i++;p--;
		}
		else if(a[i]==a[q+1]&&i<q+1)
		{
			ans[k]=i;
			ans[2*n+1-k]=q+1;		
			//cout<<"b "<<i<<" "<<j<<" "<<p<<" "<<q+1<<endl; 		
			i++;q++;
		}
		else if(a[j]==a[p-1]&&p-1<j)
		{
			ans[k]=j;
			ans[2*n+1-k]=p-1;			
			//cout<<"c "<<i<<" "<<j<<" "<<p-1<<" "<<q<<endl; 	
			j--;p--;
		}
		else if(a[j]==a[q+1]&&q+1<j)
		{
			ans[k]=j;
			ans[2*n+1-k]=q+1;			
			//cout<<"d "<<i<<" "<<j<<" "<<p<<" "<<q+1<<endl;		
			j--;q++;
		}
		else
		{
			return 0;
		}
	}
	return 1;
}
void print()
{
	int l=1,r=2*n;
	for(int i=1;i<=2*n;i++)
	{		
		//cout<<"ans "<<i<<" "<<ans[i]<<endl;
		//cout<<l<<" "<<r<<endl;	
		if(ans[i]==l)
		{
			printf("L");
			l++;
		}
		else
		{
			printf("R");
			r--;
		}
	}
	printf("\n");
 } 
void clear()
{
	for(int i=0;i<N;i++)
	{
		a[i]=0;
		ans[i]=0;
		pos[i]=0;
		to[i]=0;
	}
}
int main()
{
	//freopen("7915.in","r",stdin);
	//freopen("7915.out","w",stdout);
	int T,i;
	cin>>T;
	while(T--)
	{
		scanf("%d",&n);
		clear();
		for(i=1;i<=2*n;i++)
		{
			scanf("%d",&a[i]);
			if(!pos[a[i]]) pos[a[i]]=i;
			else
			{
				to[pos[a[i]]]=i;
				to[i]=pos[a[i]];
			}
		}
		ans[1]=1;ans[2*n]=to[1];
		if(find(1,to[1]))
		{
			//cout<<"ok1"<<endl;
			print();
			continue;
		}
		ans[1]=2*n;ans[2*n]=to[2*n];
		if(find(2*n,to[2*n]))
		{
			//cout<<"ok2"<<endl;
			print();
			continue;
		}
		printf("-1\n");
	}
	return 0;
}
2021/11/8 21:19
加载中...