求调 96 pts
查看原帖
求调 96 pts
1369607
luckyqwq楼主2024/10/24 16:00
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int T, k;
int n, a[N];
deque < int > d1, d2;
int add ()
{
	
	string s1 = "L", s2 = "";
	while (d1.size() || d2.size())
	{
		if (d1.size() > 1 && d1.front() == d1.back())
		{
			s1 = s1 + 'L';
			s2 = 'L' + s2;
			d1.pop_front();
			d1.pop_back ();
		}
		else if (d2.size() > 1 && d2.front() == d2.back())
		{
			s1 = s1 + 'R';
			s2 = 'R' + s2;
			d2.pop_front();
			d2.pop_back ();
		}
		else if (d1.size() && d2.size() && d1.front() == d2.back())
		{
			s1 = s1 + 'L';
			s2 = 'R' + s2; 
			d1.pop_front();
			d2.pop_back ();
		}
		else if (d1.size() && d2.size() && d2.front() == d1.back())
		{
			s1 = s1 + 'R';
			s2 = 'L' + s2;
			d2.pop_front();
			d1.pop_back ();
		}
		else
		{
			return 0;
		}
	}
	cout << s1 + s2 + 'L' << "\n";
	return 1;
}
int addd ()
{
	string s1 = "R", s2 = "";
	while (d1.size() || d2.size())
	{
		if (d1.size() > 1 && d1.front() == d1.back())
		{
			s1 = s1 + 'L';
			s2 = 'L' + s2;
			d1.pop_front();
			d1.pop_back ();
		}
		else if (d2.size() > 1 && d2.front() == d2.back())
		{
			s1 = s1 + 'R';
			s2 = 'R' + s2;
			d2.pop_front();
			d2.pop_back ();
		}
		else if (d1.size() && d2.size() && d1.front() == d2.back())
		{
			s1 = s1 + 'L';
			s2 = 'R' + s2; 
			d1.pop_front();
			d2.pop_back ();
		}
		else if (d1.size() && d2.size() && d2.front() == d1.back())
		{
			s1 = s1 + 'R';
			s2 = 'L' + s2;
			d2.pop_front();
			d1.pop_back ();
		}
		else
		{
			return 0;
		}
	}
	cout << s1 + s2 + 'L' << "\n";
	return 1;
}
signed main() {
//	freopen ("palin2.in", "r", stdin);
//	freopen ("palin2.out", "w", stdout);
	cin >> T;
	while (T --)
	{
		cin >> n;
		n *= 2;
		while (d1.size())
		{
			d1.pop_front();
		}
		while (d2.size())
		{
			d2.pop_front();
		}
		for (int i = 1;i <= n; ++ i)
		{
			cin >> a[i];
		} 
		for (int i = 2;i <= n; ++ i)
		{
			if (a[i] == a[1])
			{
				k = i;
				break;
			}
		}
		for (int i = 2;i < k; ++ i)
		{
			d1.push_back (a[i]);
		}
		for (int i = k + 1;i <= n; ++ i)
		{
			d2.push_front (a[i]);
		}
		if(add () == 1)
		{
			continue;
		}
		while (d1.size())
		{
			d1.pop_front();
		}
		while (d2.size())
		{
			d2.pop_front();
		}
		for (int i = 1;i < n; ++ i)
		{
			if (a[i] == a[n])
			{
				k = i;
				break;
			}
		}
		for (int i = 1;i < k; ++ i)
		{
			d1.push_back (a[i]);
		}
		for (int i = k + 1;i < n; ++ i)
		{
			d2.push_front (a[i]);
		}
		if(addd () == 1)
		{
			continue;
		}
		cout << "-1\n";
	}
	return 0;
}
//2
//5
//4 1 2 4 5 3 1 2 3 5
2024/10/24 16:00
加载中...