526互联

AtCoder Regular Contest 141 C Bracket and Permutation

发布时间 2023-06-13 22:00:02作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑给出 \(S\)，如何求 \(P, Q\)。先考虑 \(P\)，那我们肯定想让 \(P\) 的每一项都尽量往前靠。设 \([1, k]\) 为合法括号串，\(S_{k + 1} = \texttt{)}\)，那 \(P\) 的前 \(k\) 项依次为 \(1 \sim k\)，第 \(k + 1\) 项不能为 \(k + 1\) 了，那找到 \(k + 1\) 之后的第一个左括号，设其位置为 \(p\)，那 \(P_{k + 1} = p, P_{k + 2} = k + 1\)。一直如此直到某个时刻，前缀左括号数和右括号数相等，并且下一个字符是左括号，那就回到了一开始的情况，从这个左括号往后填。这样可以求出 \(P\)，求 \(Q\) 类似地可以从后往前就变成了求 \(P\)。

考虑画出折线图，那可以发现，\(x = 0\) 上方部分可以依次填不需要改动顺序，\(x = 0\) 下方就先找到从左往右第一个之前没选过的左括号，和第一个之前没选过的右括号配对。

现在考虑原题，给出 \(P, Q\)，构造 \(S\)。先暂时不考虑无解情况。发现如果 \(P_{2i - 1} < P_{2i}\)，这一段一定在 \(x = 0\) 上方；如果 \(P_{2i - 1} > P_{2i}\)，这一段一定在 \(x = 0\) 下方，并且可以确定 \(S_{2i - 1} = \texttt{(}, S_{2i} = \texttt{)}\)。那我们可以确定，折线在 \(x = 0\) 下方部分的 \(S\) 了。这时候我们惊喜地发现，因为求 \(Q\) 的过程是反过来的，所以可以类似地，根据 \(Q_{2i - 1} < Q_{2i}\) 确定折线在 \(x = 0\) 上方部分的 \(S\)。两个合在一起，我们发现 \(S\) 可以被唯一确定！

但是你先别急，还没做完。因为我们发现有很多繁琐的无解情况需要特判。若 \(S\) 还有没被确定的部分，就一定无解；否则可以根据 \(S\) 求出 \(P, Q\)，验证是否和题目给出的 \(P, Q\) 一致即可。

时间复杂度是优秀的 \(O(n)\)。

code 
// Problem: C - Bracket and Permutation
// Contest: AtCoder - AtCoder Regular Contest 141
// URL: https://atcoder.jp/contests/arc141/tasks/arc141_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;

int n, a[maxn], b[maxn], c[maxn];
char s[maxn];

void solve() {
	scanf("%d", &n);
	n <<= 1;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; i += 2) {
		if (a[i] > a[i + 1]) {
			s[a[i]] = '(';
			s[a[i + 1]] = ')';
		}
	}
	for (int i = 1; i <= n; i += 2) {
		if (b[i] < b[i + 1]) {
			if (s[b[i]] == ')' || s[b[i + 1]] == '(') {
				puts("-1");
				return;
			}
			s[b[i]] = '(';
			s[b[i + 1]] = ')';
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (!s[i]) {
			puts("-1");
			return;
		}
	}
	int k = 0, lst = 1, tot = 0;
	for (int i = 1; i <= n; ++i) {
		k += (s[i] == '(' ? 1 : -1);
		if (!k) {
			if (s[lst] == '(') {
				for (int j = lst; j <= i; ++j) {
					c[++tot] = j;
				}
			} else {
				vector<int> vl, vr;
				for (int j = lst; j <= i; ++j) {
					if (s[j] == '(') {
						vl.pb(j);
					} else {
						vr.pb(j);
					}
				}
				for (int j = 0; j < (i - lst + 1) / 2; ++j) {
					c[++tot] = vl[j];
					c[++tot] = vr[j];
				}
			}
			lst = i + 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (c[i] != a[i]) {
			puts("-1");
			return;
		}
	}
	k = 0;
	lst = n;
	tot = 0;
	for (int i = n; i; --i) {
		k += (s[i] == '(' ? 1 : -1);
		if (!k) {
			if (s[lst] == '(') {
				for (int j = lst; j >= i; --j) {
					c[++tot] = j;
				}
			} else {
				vector<int> vl, vr;
				for (int j = lst; j >= i; --j) {
					if (s[j] == '(') {
						vl.pb(j);
					} else {
						vr.pb(j);
					}
				}
				for (int j = 0; j < (lst - i + 1) / 2; ++j) {
					c[++tot] = vl[j];
					c[++tot] = vr[j];
				}
			}
			lst = i - 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (c[i] != b[i]) {
			puts("-1");
			return;
		}
	}
	printf("%s\n", s + 1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

一定要多思考，不能怠惰啊。