96分,#17和#26WA
查看原帖
96分,#17和#26WA
1210299
Bohan_Jiang楼主2024/10/5 16:16
#include <bits/stdc++.h>
using namespace std;

const int maxN = 500005;
int T, n, N, x, a[maxN], p[maxN], q[maxN], pt, ph, qt, qh, rt, rh;
char res[maxN];

int main() 
{
//	freopen("palin2.in", "r", stdin);
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		cin >> n;
		N = 2*n;
		memset(a, 0, sizeof a);
		memset(p, 0, sizeof p);
		memset(q, 0, sizeof q);
		memset(res, '\0', sizeof(res));
		pt = qt = rt = 0, ph = qh = 1, rh = N - 1;
		for (int i = 1; i <= N; ++i) {
			cin >> a[i];
			if (i != 1 && a[i] == a[1]) x = i;
		}
		for (int i = x-1; i > 1; --i) p[++pt] = a[i];
		for (int i = x+1; i <= N; ++i) q[++qt] = a[i];
		res[rt++] = res[rh--] = 'L';
		for (int i = 1; i <= n-1; ++i) {
			if (p[pt] == p[ph] && pt != ph && p[pt]) p[pt--] = p[ph++] = 0, res[rt++] = res[rh--] = 'L';
			else if (p[pt] == q[qh] && p[pt]) p[pt--] = q[qh++] = 0, res[rt++] = 'L', res[rh--] = 'R';
			else if (q[qt] == p[ph] && q[qt]) q[qt--] = p[ph++] = 0, res[rt++] = 'R', res[rh--] = 'L';
			else if (q[qt] == q[qh] && qt != qh && q[qt]) q[qt--] = q[qh++] = 0, res[rt++] = res[rh--] = 'R';
			else {memset(res, '\0', sizeof(res)); res[0] = '-', res[1] = '1'; break;}
		}
		if (res[0] == 'L') {cout << res << endl; continue;}
		else {
		memset(p, 0, sizeof p);
		memset(q, 0, sizeof q);
		memset(res, '\0', sizeof(res));
		pt = qt = rt = 0, ph = qh = 1, rh = N - 1;
		for (int i = 1; i <= N-1; ++i) {
			if (a[i] == a[N]) x = i;
		}
		for (int i = x-1; i >= 1; --i) p[++pt] = a[i];
		for (int i = x+1; i < N; ++i) q[++qt] = a[i];
		res[rt++] = 'R', res[rh--] = 'L';
		for (int i = 1; i <= n-1; ++i) {
			if (p[pt] == p[ph] && pt != ph && p[pt]) p[pt--] = p[ph++] = 0, res[rt++] = res[rh--] = 'L';
			else if (p[pt] == q[qh] && p[pt]) p[pt--] = q[qh++] = 0, res[rt++] = 'L', res[rh--] = 'R';
			else if (q[qt] == p[ph] && q[qt]) q[qt--] = p[ph++] = 0, res[rt++] = 'R', res[rh--] = 'L';
			else if (q[qt] == q[qh] && qt != qh && q[qt]) q[qt--] = q[qh++] = 0, res[rt++] = res[rh--] = 'R';
			else {memset(res, '\0', sizeof(res)); res[0] = '-', res[1] = '1'; break;}
		}
		cout << res << endl;
		}
	}
	return 0;
}
2024/10/5 16:16
加载中...