96ptsTLE求条(玄关
查看原帖
96ptsTLE求条(玄关
958732
DYF6friend楼主2024/10/18 20:49
#include<bits/stdc++.h>
using namespace std;
int num[500050];
int num_pos[1000050];
int main()
{
	//freopen("palin1.in","r",stdin);
	//freopen("palin.ans","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		memset(num,0,sizeof(num));
		memset(num_pos,0,sizeof(num_pos));
		int n;
		scanf("%d",&n);
		for (int i=1;i<=2*n;i++)
		{
			int x;
			scanf("%d",&x);
			if (!num[x])num[x]=i;
			else
			{
				num_pos[i]=num[x];
				num_pos[num[x]]=i;
			}
		}
		int tmp=num_pos[1];
		int ll,lr,rl,rr;
		string s1,s2;
		s1=s2="";
		ll=2;
		lr=tmp-1;
		rl=tmp+1;
		rr=2*n;
		s1=s2="L";
		bool flag=0;
		while (lr>=ll||rr>=rl)
		{
			if (ll<lr&&num_pos[ll]==lr)
			{
				s1=s1+"L";
				s2="L"+s2;
				ll++;
				lr--;
				continue;
			}
			if (ll<=lr&&rl<=rr&&num_pos[ll]==rl)
			{
				s1=s1+"L";
				s2="R"+s2;
				ll++;
				rl++;
				continue;
			}
			if (ll<=lr&&rl<=rr&&num_pos[rr]==lr)
			{
				s1=s1+"R";
				s2="L"+s2;
				rr--;
				lr--;
				continue;
			}
			if (rl<rr&&num_pos[rl]==rr)
			{
				s1=s1+"R";
				s2="R"+s2;
				rl++;
				rr--;
				continue;
			}
			flag=1;
			break;
		}
		if (!flag){cout<<s1<<s2<<endl;continue;}
	
	/*------------------------dividing line------------------------*/
		tmp=num_pos[2*n];
		ll=1;
		lr=tmp-1;
		rl=tmp+1;
		rr=2*n-1;
		s1="R";s2="L";
		flag=0;
		while (lr>=ll||rr>=rl)
		{
			if (ll<lr&&num_pos[ll]==lr)
			{
				s1=s1+"L";
				s2="L"+s2;
				ll++;
				lr--;
				continue;
			}
			if (ll<=lr&&rl<=rr&&num_pos[ll]==rl)
			{
				s1=s1+"L";
				s2="R"+s2;
				ll++;
				rl++;
				continue;
			}
			if (ll<=lr&&rl<=rr&&num_pos[rr]==lr)
			{
				s1=s1+"R";
				s2="L"+s2;
				rr--;
				lr--;
				continue;
			}
			if (rl<rr&&num_pos[rl]==rr)
			{
				s1=s1+"R";
				s2="R"+s2;
				rl++;
				rr--;
				continue;
			}
			flag=1;
			break;
		}
		if (!flag){cout<<s1<<s2<<endl;continue;}
		cout<<-1<<endl;
	} 
 } 
2024/10/18 20:49
加载中...