40分TLE求助大佬。
查看原帖
40分TLE求助大佬。
452610
csy20070918楼主2022/10/16 00:05
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10;
int opr[MAXN] = {-1},wher[MAXN];
bool fi,flagall;
int dq[MAXN];
vector<int> p;
bool check(int x,int rank,int pos){
	if (rank > x){
		if (wher[2*x+1-rank] != p[pos]) return false;
	}
	if (rank <= x){
		for (int i = 1;i < rank;i++){
			if (dq[i] == p[pos]) return false;
		}
	}
	return true;
}
void solve(int x,int rank,bool flag,int head,int rear){
	if (rank > 2*x || flagall == true || fi == true) return;
	if (flag == true && fi == false){
		dq[rank] = p[head];
		opr[rank] = 0;
		if (check(x,rank,head) == false) return;
		if (rank <= x) wher[rank] = p[head];
		head++; 
	}else if (flag == false && fi == false){
		dq[rank] = p[rear];
		opr[rank] = 1;
		if (check(x,rank,rear) == false) return;
		if (rank <= x) wher[rank] = p[rear];
		rear--;
	}
	if (rank == 2*x){
		flagall = true;
		fi = true;
		return;
	}
	if (fi == false) solve(x,rank+1,1,head,rear);
	if (fi == false) solve(x,rank+1,0,head,rear);
}
int main(){
	int n;
	cin >> n;
	for (int i = 0;i < n;i++){
		fi = false,flagall = false;
		p.clear();
		int x;
		cin >> x;
		for (int j = 0;j <= 2*x;j++){
			opr[j] = -1,wher[j] = 0,dq[j] = 0;
		}
		for (int j = 0;j < 2*x;j++){
			int y;
			cin >> y;
			p.push_back(y);
		}
		solve(x,1,1,0,2*x-1);
		if (flagall == false) solve(x,1,0,0,2*x-1);
		if (flagall == false){
			cout << -1 << endl;
			continue;
		}
		if (opr[1] != -1){
			for (int i = 1;i <= 2*x;i++){
				if (opr[i] == 0) cout << "L";
				else cout << "R";
			}
			cout << endl;
		}else{
			cout << -1 << endl;
		}
	
	}
	return 0;
}
2022/10/16 00:05
加载中...