96,已经优化的不能再优化了www
查看原帖
96,已经优化的不能再优化了www
637220
wooaoo楼主2024/10/22 11:18
#include <bits/stdc++.h>
//O(nT)
using namespace std;
int T;
int v[2*500005],pos1,pos2n;
list<int>l1,l2;
void work()
{
	int n,rfirst=0;
	cin>>n;
	pos1=0,pos2n=0;
	for(int i=1;i<=2*n;i++)
	{
		cin>>v[i];
		if(v[i]==v[1]&&i!=1)pos1=i;
	}
	for(int i=2*n-1;i>=1;i--)
	if(v[i]==v[2*n])
	{
		pos2n=i;
		break;
	}
	l1.clear(),l2.clear();
	string ans1="L",ans2="";
	/////// L first
	for(int i=2;i<pos1;i++)l1.push_back(v[i]);
	for(int i=pos1+1;i<=2*n;i++)l2.push_back(v[i]);
	for(int i=2;i<=n;i++)
	{
		int a1=-1,a2=-2,a3=-3,a4=-4;
		int l1size1=0,l2size1=0;
		if(l1.size())a1=l1.front(),a2=l1.back();
		if(l2.size())a3=l2.front(),a4=l2.back();
		if(l1.size()==1)l1size1=1;
		if(l2.size()==1)l2size1=1;
		if(a1==a2)
		{
			if(l1size1==1);
			else 
			{
				ans1=ans1+"L";
				ans2=ans2+"L";
				l1.pop_front(),l1.pop_back();
				continue;
			}
		}
		if(a1==a3)
		{
			ans1=ans1+"L";
			ans2=ans2+"R";
			l1.pop_front(),l2.pop_front();
			continue;
		}
		if(a4==a2)
		{
			ans1=ans1+"R";
			ans2=ans2+"L";
			l2.pop_back(),l1.pop_back();
			continue;
		}
		if(a4==a3)
		{
			if(l2size1==1);
			else 
			{
				ans1=ans1+"R";
				ans2=ans2+"R";
				l2.pop_front(),l2.pop_back();
				continue;
			}
		}
		rfirst=1;
		break;
	}
	if(rfirst==0)
	{
		cout<<ans1;
		for(int i=ans2.length()-1;i>=0;i--)cout<<ans2[i];
		cout<<"L\n";
		return;
	}
	
	ans1="R",ans2="";
	l1.clear(),l2.clear();
	/////// R first
	for(int i=1;i<pos2n;i++)l1.push_back(v[i]);
	for(int i=pos2n+1;i<2*n;i++)l2.push_back(v[i]);
	for(int i=2;i<=n;i++)
	{
		int a1=-1,a2=-2,a3=-3,a4=-4;
		int l1size1=0,l2size1=0;
		if(l1.size())a1=l1.front(),a2=l1.back();
		if(l2.size())a3=l2.front(),a4=l2.back();
		if(l1.size()==1)l1size1=1;
		if(l2.size()==1)l2size1=1;
		if(a1==a2)
		{
			if(l1size1==1);
			else 
			{
				ans1=ans1+"L";
				ans2=ans2+"L";
				l1.pop_front(),l1.pop_back();
				continue;
			}
		}
		if(a1==a3)
		{
			ans1=ans1+"L";
			ans2=ans2+"R";
			l1.pop_front(),l2.pop_front();
			continue;
		}
		if(a4==a2)
		{
			ans1=ans1+"R";
			ans2=ans2+"L";
			l2.pop_back(),l1.pop_back();
			continue;
		}
		if(a4==a3)
		{
			if(l2size1==1);
			else 
			{
				ans1=ans1+"R";
				ans2=ans2+"R";
				l2.pop_front(),l2.pop_back();
				continue;
			}
		}
		cout<<"-1\n";
		return;
	}
	cout<<ans1;
	for(int i=ans2.length()-1;i>=0;i--)cout<<ans2[i];
	cout<<"L\n";
	return;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)work();
	return 0;
}
2024/10/22 11:18
加载中...