蒟蒻 96pts求助 WA #17 #26
查看原帖
蒟蒻 96pts求助 WA #17 #26
450237
Calvin0221楼主2022/9/19 13:33
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 5e5 + 1;
const int maxm = maxn << 1;
int t,n,a[maxm],b[maxm];
int l[maxn],r[maxn];
char res[maxn];
bool solve(int idx,int Left,int Right){
	res[1] = (Left == 2) ? 'L' : 'R';
	int tmpl = idx,tmpr = idx;
	int Start = 2,End = 2 * n - 1;
	for(int i=1;i<n;i++){
		     if (r[a[Left]] == tmpl - 1) tmpl--, Left++,res[Start++] = 'L',res[End--] = 'L';
		else if (r[a[Left]] == tmpr + 1) tmpr++, Left++,res[Start++] = 'L',res[End--] = 'R';
		else if(l[a[Right]] == tmpl - 1) tmpl--,Right--,res[Start++] = 'R',res[End--] = 'L';
		else if(l[a[Right]] == tmpr + 1) tmpr++,Right--,res[Start++] = 'R',res[End--] = 'R';
		else return false; 
	}
	res[2 * n] = 'L';
	printf("%s\n",res + 1);
	return true;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(res,0,sizeof(res));
		for(int i=1;i<=2*n;i++) scanf("%lld",&a[i]);
		for(int i=1;i<=2*n;i++){
			if(l[a[i]]) r[a[i]] = i;
			else        l[a[i]] = i;
		}
		if(solve(r[a[1]],2,2 * n)) continue;
		if(solve(l[a[2 * n]],1,2 * n - 1)) continue;
		puts("-1");
	}
	return 0;
}
2022/9/19 13:33
加载中...