手写 deque 求调,3 关注为报
查看原帖
手写 deque 求调,3 关注为报
398190
lanretE楼主2022/7/10 21:39

rt,样例过不了,但是自己把样例带进去模拟了一遍没发现问题

#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ll long long
#define qwq cout<<"QwQ"<<endl;
using namespace std;
const int N=1000010;
int a[N],b[N],c[N],n;
int q1[N],q2[N];
bool solve(char ch){
	for(int i=0;i<=n;++i) q1[i]=0,q2[i]=0;
	int t1=0,t2=0,h1=1,h2=1;
	string ans,s; ans.clear(); s.clear();
	ans+=ch;
	s+='L';
	if(ch=='L'){
		for(int i=2;i<c[1];++i) q1[++t1]=i;
		for(int i=n;i>c[i];--i) q2[++t2]=i;
	}
	else{
		for(int i=1;i<c[n];++i) q1[++t1]=i;
		for(int i=n-1;i>c[n];--i) q2[++t2]=i;
	}
	while(h1<=t1 || h2<=t2){
		int x1=h1<=t1?h1:0;
		int x2=h2<=t2?h2:0;
		int y1=h1<=t1?t1:0;
		int y2=h2<=t2?t2:0;
		if(c[x1]==y1){
			ans+='L';
			s+='L';
			++h1; --t1;
		}
		else if(c[x1]==y2){
			ans+='L';
			s+='R';
			++h1; --t2;
		}
		else if(c[x2]==y1){
			ans+='R';
			s+='L';
			++h2; --t1;
		}
		else if(c[x2]==y2){
			ans+='R';
			s+='R';
			++h2; --t2;
		}
		else return 0;
	}
	reverse(s.begin(),s.end());
	ans+=s;
	cout<<ans<<endl;
	return 1;
}
int main(){
	int T; cin>>T;
	while(T--){
		cin>>n; n<<=1;
		for(int i=0;i<=n;++i) b[i]=0;
		c[0]=-1;
		for(int i=1;i<=n;++i){
			cin>>a[i];
			if(b[a[i]]){
				c[b[a[i]]]=i;
				c[i]=b[a[i]];
			}
			else b[a[i]]=i;
		}
		bool a1=solve('L');
		if(a1) continue;
		bool a2=solve('R');
		if(a2==0) cout<<-1<<endl;
	}
	return 0;
}

2022/7/10 21:39
加载中...