WA 成72,求指点
查看原帖
WA 成72,求指点
112395
Martin_MHT楼主2021/10/24 09:27
#include <cstdio>
#include <cstring>
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(int i = (a); i >= (b); --i)
inline void read(int &x) { //ll, ne
	x = 0; char ch = getchar();
	while(ch < '0' || ch > '9')	ch = getchar();
	while(ch >= '0' && ch <= '9')	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
}
const int N = 5e5 + 10;
int T, n, tot, p[N], an[N << 1], a[N << 1], f[N];
bool fx[N << 1];
bool op[N << 1];
void L() {op[++tot] = 0;}
void R() {op[++tot] = 1;}
void print(bool flag) {
	if(flag) {
		fo(i, 1, n << 1)	putchar(op[i] ? 'R' : 'L');
		puts("");
	}
	else puts("-1");
}
void work() {
	tot = 0;
	int l = 1, r = n << 1;
	fo(i, 1, n) {
		if(a[l] == f[i] && a[r] == f[i])	fx[a[l]] ? (--r, R()) : (++l, L());
		else if(a[l] == f[i]) L(), ++l;
		else if(a[r] == f[i])	R(), --r;
	}
	fd(i, n, 1) {
		if(a[l] == f[i]) L(), ++l;
		else if(a[r] == f[i])	R(), --r;
	}
}
bool solv2(int t, int l, int r, bool x) {
	if(l > r || (r - l + 1) & 1)	return 0;
	for(int i = l, j = r, k = t; i <= j; ++i, --j, ++k) {
		if(a[i] ^ a[j])	return 0;
		f[k] = a[i], fx[k] = x;
	}
	return 1;
}
bool solve(int t, int l1, int r1, int l2, int r2) {
	if(t > n)
		return 1;
	if(l1 > r1 || l2 > r2)
		return solv2(t, l1, r1, 0) || solv2(t, l2, r2, 1);
	if(an[l1] == r1 || an[l1] == l2) {
		f[t] = a[l1];
		fx[a[l1]] = 0;
		if(an[l1] == r1)
			return solve(t + 1, l1 + 1, r1 - 1, l2, r2);
		else return solve(t + 1, l1 + 1, r1, l2 + 1, r2);
	}
	else if(an[r2] == r1 || an[r2] == l2) {
		f[t] = a[r2];
		fx[a[r2]] = 1;
		if(an[r2] == r1)
			return solve(t + 1, l1, r1 - 1, l2, r2 - 1);
		else return solve(t + 1, l1, r1, l2 + 1, r2 - 1);
	}
	return 0;
}
int main() {
	freopen("palin.in", "r", stdin);
	freopen("palin.out", "w", stdout);
	for(read(T); T; --T) {
		read(n);
		fo(i, 1, n)	p[i] = 0;
		fo(i, 1, n << 1) {
			read(a[i]);
			if(p[a[i]])	an[p[a[i]]] = i, an[i] = p[a[i]];
			else	p[a[i]] = i;
		}
		if(f[1] = a[1], solve(2, 2, an[1] - 1, an[1] + 1, n << 1))
			work(), print(1);
		else if(f[1] = a[n << 1], solve(2, 1, an[n << 1] - 1, an[n << 1] + 1, n * 2 - 1))
			work(), print(1);
		else	print(0);
	}
	return 0;
}

2021/10/24 09:27
加载中...