T了2个点求助,理论O(N)
查看原帖
T了2个点求助,理论O(N)
95780
a1589255859楼主2021/10/27 12:38
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read()
{
	int a=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c)){a=a*10+c-'0';c=getchar();}
	return a;
}
int a[500005],b[1000005];
int l1,r1,l2,r2;
pair<bool,string>k;
inline pair<bool,string>p()
{
	if(l1<l2&&b[l1]==l2)
	{
		l1++;l2--;
		pair<bool,string>v=p();
		v.second="L"+v.second+"L";
		return v;
	}
	if(l1<=l2&&r2<=r1&&b[l1]==r2)
	{
		l1++;r2++;
		pair<bool,string>v=p();
		v.second="L"+v.second+"R";
		return v;
	}
	if(l1<=l2&&r2<=r1&&b[r1]==l2)
	{
		r1--;l2--;
		pair<bool,string>v=p();
		v.second="R"+v.second+"L";
		return v;
	}
	if(r2<r1&&b[r1]==r2)
	{
		r1--;r2++;
		pair<bool,string>v=p();
		v.second="R"+v.second+"R";
		return v;
	}
	//printf("%d %d %d %d\n",l1,r1,l2,r2);
	if(l1>l2&&r1<r2)return make_pair(1,"");
	return make_pair(0,"");
}
int main()
{
	//freopen("palin.in","r",stdin);
	//freopen("palin.out","w",stdout);
	int t=read();
	while(t--)
	{
		memset(a,0,sizeof a);
		memset(b,0,sizeof(b));
		int n=read();
		for(re int i=1;i<=2*n;++i)
		{
			int p=read();
			if(a[p])b[a[p]]=i,b[i]=a[p];
			else a[p]=i;
		}
		l1=2,r1=2*n,l2=b[1]-1,r2=b[1]+1;
		k=p();k.second="L"+k.second+"L";
		if(k.first){cout<<k.second;putchar('\n');continue;}
		l1=1,r1=2*n-1,l2=b[n*2]-1,r2=b[n*2]+1;
		k=p();k.second="R"+k.second+"L";
		if(k.first){cout<<k.second;putchar('\n');continue;}
		printf("-1\n");
	}
	return 0;
}
2021/10/27 12:38
加载中...