24分WA求调
查看原帖
24分WA求调
553276
fluoxetine_楼主2023/7/24 22:54

闰土,代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <queue>
using namespace std;

const int N = 5e5 + 10;

int T, pos, n; 

int q[N * 2];

char cur[N], ans[N];

deque<int> eq1, eq2;

int find_(int head, int tail, int judge)
{
	for(int i = head; i <= tail; i++)
		if(q[i] == judge)
			return i;
}

void work()
{
	int now = 2;
	while(1)
	{
		if(eq1.empty() && eq2.empty())
			break;
		else if(eq2.empty())
		{
			if(eq1.front() != eq1.back())
			{
				cur[1] = 'q';
				return ;
			}
			cur[now] = cur[2 * n - now + 1] = 'L';
			eq1.pop_front();
			eq1.pop_back();
		}
		else if(eq1.empty())
		{
			if(eq2.front() != eq2.back())
			{
				cur[1] = 'q';
				return ;
			}
			cur[now] = cur[2 * n - now + 1] = 'R';
			eq2.pop_front();
			eq2.pop_back();
		}
		else
		{
			if(eq1.back() == eq1.front() && eq1.size() > 1)
			{
				cur[now] = cur[2 * n - now + 1] = 'L';
				eq1.pop_back();
				eq1.pop_front();
			}
			else if(eq1.back() == eq2.front())
			{
				cur[now] = 'L';
				cur[2 * n - now + 1] = 'R';
				eq2.pop_front();
				eq1.pop_back();
			}
			else if(eq2.back() == eq1.front())
			{
				cur[now] = 'R';
				cur[2 * n - now + 1] = 'L';
				eq1.pop_front();
				eq2.pop_back();
			}
			else if(eq2.back() == eq2.front() && eq2.size() > 1){
				cur[now] = 'R';
				cur[2 * n - now + 1] = 'R';
				eq2.pop_back();
				eq2.pop_front();
			}
			else
			{
				cur[1] = 'q';
				return ;
			}
		}
		now++;
	}
	return ;
}
bool jud()
{
	int iter = 1;
	while(iter <= 2 * n && cur[iter] == ans[iter]) iter++;
	return iter <= 2 * n && cur[iter] < ans[iter];
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
    	memset(ans, 0, sizeof ans);
    	ans[1] = 'e';
    	scanf("%d", &n);
    	for(int i = 1; i <= 2 * n ; i++)
			scanf("%d", q + i);
		eq1.clear(), eq2.clear();
		pos = find_(2, 2 * n, q[1]);
		for(int i = 2; i <= pos - 1; i++)
			eq1.push_back(q[i]);
		for(int i = pos + 1; i <= 2 * n; i++)
			eq2.push_front(q[i]);
		cur[1] = 'L';
		cur[2 * n] = 'L';
		work();
		if(jud())
			for(int i = 1; i <= 2 * n; i++)
				ans[i] = cur[i];
		
		eq1.clear(), eq2.clear();
		pos = find_(1, 2 * n - 1, q[2 * n]);
		for(int i = 1; i <= pos - 1; i++)
			eq1.push_back(q[i]);
		for(int i = pos + 1; i <= 2 * n - 1; i++)
			eq2.push_front(q[i]);
		cur[1] = 'R';
		cur[2 * n] = 'L';
		work();
		if(jud())
			for(int i = 1; i <= 2 * n; i++)
				ans[i] = cur[i];
				
		if(ans[1] == 'e')
			printf("-1");
		else
			for(int i = 1; i <= 2 * n; i++)
				printf("%c", ans[i]);
		puts("");
	}
	return 0;
}
2023/7/24 22:54
加载中...