玄关求条12pts
查看原帖
玄关求条12pts
551430
__O__o__楼主2024/10/23 21:35
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[500005],b[500005],st1_top,st1_tail,st2_top,st2_tail;
int n;
string ans1,ans2;
inline bool solve(int l1,int r1,int l2,int r2)
{
//	memset(l,0,sizeof(l));
//	memset(r,0,sizeof(r));
	st1_top=l1,st1_tail=r1,st2_top=l2,st2_tail=r2;
	for(int i=1;i<n;i++)
	{
		if(st1_top<=st1_tail&&((st2_top<=st2_tail&&a[st1_top]==a[st2_top])||(st1_top<st1_tail&&a[st1_top]==a[st1_tail])))
		{
			if(st1_top<st1_tail&&a[st1_top]==a[st1_tail])
			{
				
				st1_top++,st1_tail--;
//				ans[i]='L',ans[2*(n-1)-i+1]='L';
                ans1.push_back('L');
                ans2.push_back('L');
			}
			else
			{
				st1_top++,st2_top++;
//				ans[i]='L',ans[2*(n-1)-i+1]='R';
				ans1.push_back('L');
                ans2.push_back('R');
			}
		}
		else if(st2_top<=st2_tail&&((st1_top<=st1_tail&&a[st1_tail]==a[st1_tail])||(st2_top<st2_tail&&a[st2_top]==a[st2_tail])))
		{
			if(st2_top<=st2_tail&&a[st2_top]==a[st2_tail])
			{
				st2_top++,st2_tail--;
//				ans[i]='R',ans[2*(n-1)-i+1]='R';
				ans1.push_back('R');
                ans2.push_back('R');
			}
			else
			{
				st2_tail--,st1_tail--;
//				ans[i]='R',ans[2*(n-1)-i+1]='L';
				ans1.push_back('R');
                ans2.push_back('L');
			}
		}
		else return 0;
	}
	return 1;
//	reverse(ans.begin(),ans.end());
}
void init_main()
{
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=2;
	}
	st1_top=st1_tail=st2_top=st2_tail=0;
	int f1=0,f2=0;
	for(int i=2;i<=2*n;i++)
	{
		if(a[i]==a[1])
		{
			f1=i;break;
		}
	}
	for(int i=1;i<2*n;i++)
	{
		if(a[i]==a[2*n]) 
		{
			f2=i;break;
		}
	}
	if(solve(2,f1-1,f1+1,2*n))
	{
		reverse(ans2.begin(),ans2.end());
		cout<<'L'<<ans1<<ans2<<'L';
	}
	else if(solve(1,f2-1,f2+1,2*n-1))
	{
		reverse(ans2.begin(),ans2.end());
		cout<<'R'<<ans1<<ans2<<'L';
	}
	else 
	{
		cout<<"-1";
	}
	cout<<'\n';
	ans1.clear(),ans2.clear();
}
int main()
{
//	freopen("palin2.in","r",stdin);
//	freopen("palin2.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		init_main();
	}
	return 0;
}
2024/10/23 21:35
加载中...