萌新双端队列求助,24pts
查看原帖
萌新双端队列求助,24pts
232507
OK咯莫名其妙楼主2021/11/28 17:05
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int n;
int v[maxn];
char ans[maxn],cur[maxn];
int see(int l,int r,int val) {
	for(int i=l; i<=r; i++)
		if(v[i]==val)
			return i;
	return -1;
}
deque<int> a,b;
void check() {
	int now=2;
	while(1) {
		if(a.empty() && b.empty()) {
			break;
		} else if(b.empty()) {
			if(a.front()!=a.back()) {
				cur[1]='Z';
				return ;
			}
			cur[now]=cur[2*n-now+1]='L';
			a.pop_front();
			a.pop_back();
		} else if(a.empty()) {
			if(b.front()!=b.back()) {
				cur[1]='Z';
				return ;
			}
			cur[now]=cur[2*n-now+1]='R';
			b.pop_front();
			b.pop_back();
		} else {
			if(a.back()==a.front() && a.size()>1) {
				cur[now]=cur[2*n-now+1]='L';
				a.pop_front();
				a.pop_back();
			} else if(a.back()==b.front()) {
				cur[now]='L';
				cur[2*n-now+1]='R';
				b.pop_front();
				a.pop_back();
			} else if(b.back()==a.front()) {
				cur[now]='R';
				cur[2*n-now+1]='L';
				a.pop_front();
				b.pop_back();
			} else if(b.back()==b.front() && b.size()>1) {
				cur[now]='R';
				cur[2*n-now+1]='R';
				b.pop_front();
				b.pop_back();
			} else {
				cur[1]='Z';
				return ;
			}
		}
		now++;
	}
}
bool pan() {
	int id=1;
	while(id<=2*n && cur[id]==ans[id])
		id++;
	return id<=2*n && cur[id]<ans[id];
}
signed main() {
	int T;
	cin>>T;
	int pos;
	while(T--) {
		ans[1]='Y';
		cin>>n;
		for(int i=1; i<=2*n; i++)
			scanf("%d",v+i);

		a.clear();
		b.clear();
		pos=see(2,2*n,v[1]);
		for(int i=pos-1; i>=2; i--)
			a.push_front(v[i]);
		for(int i=pos+1; i<=2*n; i++)
			b.push_front(v[i]);
		cur[1]='L';
		cur[2*n]='L';
		check();
		if(pan()) {
			for(int i=1; i<=2*n; i++)
				ans[i]=cur[i];
		}
		a.clear();
		b.clear();
		pos=see(1,2*n-1,v[2*n]);
		for(int i=pos-1; i>=2; i--)
			a.push_back(v[i]);
		for(int i=pos+1; i<=2*n; i++)
			b.push_back(v[i]);
		cur[1]='R';
		cur[2*n]='L';
		check();
		if(pan()) {
			for(int i=1; i<=2*n; i++)
				ans[i]=cur[i];
		}
		if(ans[1]=='Y') {
			cout<<-1<<endl;
		} else {
			for(int i=1; i<=2*n; i++) cout<<ans[i];
			cout<<endl;
		}
	}
	return 0;
}
2021/11/28 17:05
加载中...