Submission #37355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
37355	2017-12-24T14:49:22 Z	cheater2k	Match (CEOI16_match)	C++14	100 / 100	56 ms	16940 KB

match

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

string s;
int n, prv[N];
int jump[N][18], mask[N][18];
char res[N];

void out() { cout << "-1\n"; exit(0); }

void solve(int l, int r) {
	if (l > r) return;
	if (s[l] == s[r]) {
		res[l] = '('; res[r] = ')'; // valid
		return solve(l + 1, r - 1);
	}

	int ch = s[l] - 'a';
	int cur = r;
	if (mask[cur][17] & (1 << ch)) {
		for (int i = 16; i >= 0; --i) if (!(mask[cur][i] & (1 << ch))) {
			cur = jump[cur][i];
		}
	} else out(); // invalid

	if (cur == -1) out();
	cur = jump[cur][0];
	if (cur <= l || s[cur] != s[l]) out(); 

	// s[cur] is the matching bracket of s[l]
	res[l] = '('; res[cur] = ')';
	solve(l + 1, cur - 1);
	solve(cur + 1, r);
}

int main() {
	cin >> s, n = s.size();
	if (n & 1) out();

	prv[0] = -1;
	for (int i = 1; i < n; ++i) {
		if (s[i] == s[i - 1]) { prv[i] = i - 1; continue; }
		int cur = i - 1;
		while(cur >= 0 && s[cur] != s[i]) {
			cur = prv[cur] - 1;
		}
		prv[i] = max(cur, -1);
	}

	// prepare for RMQ
	for (int i = 0; i < n; ++i) if (prv[i] != -1) {
		jump[i][0] = prv[i] - 1;
		if (prv[i] > 0) mask[i][0] |= (1 << s[prv[i] - 1] - 'a');
	}
	for (int j = 1; j <= 17; ++j) {
		for (int i = 0; i < n; ++i) jump[i][j] = -1;
		for (int i = 0; i < n; ++i) {
			if (jump[i][j - 1] != -1) 
				jump[i][j] = jump[jump[i][j - 1]][j - 1],
				mask[i][j] |= mask[jump[i][j - 1]][j - 1];
			mask[i][j] |= mask[i][j - 1];
		}
	}

	solve(0, n - 1);
	for (int i = 0; i < n; ++i) cout << res[i]; cout << '\n';
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:55:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   if (prv[i] > 0) mask[i][0] |= (1 << s[prv[i] - 1] - 'a');
                                                     ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	16568 KB	Output is correct
2	Correct	0 ms	16568 KB	Output is correct
3	Correct	0 ms	16568 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	16568 KB	Output is correct
2	Correct	0 ms	16568 KB	Output is correct
3	Correct	0 ms	16568 KB	Output is correct
4	Correct	0 ms	16568 KB	Output is correct
5	Correct	0 ms	16568 KB	Output is correct
6	Correct	0 ms	16568 KB	Output is correct
7	Correct	0 ms	16568 KB	Output is correct

Subtask #3

63.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	16568 KB	Output is correct
2	Correct	0 ms	16568 KB	Output is correct
3	Correct	0 ms	16568 KB	Output is correct
4	Correct	0 ms	16568 KB	Output is correct
5	Correct	0 ms	16568 KB	Output is correct
6	Correct	0 ms	16568 KB	Output is correct
7	Correct	0 ms	16568 KB	Output is correct
8	Correct	0 ms	16568 KB	Output is correct
9	Correct	0 ms	16568 KB	Output is correct
10	Correct	3 ms	16568 KB	Output is correct
11	Correct	3 ms	16568 KB	Output is correct
12	Correct	26 ms	16704 KB	Output is correct
13	Correct	29 ms	16884 KB	Output is correct
14	Correct	26 ms	16884 KB	Output is correct
15	Correct	36 ms	16884 KB	Output is correct
16	Correct	29 ms	16884 KB	Output is correct
17	Correct	36 ms	16884 KB	Output is correct
18	Correct	43 ms	16884 KB	Output is correct
19	Correct	46 ms	16884 KB	Output is correct
20	Correct	23 ms	16704 KB	Output is correct
21	Correct	56 ms	16940 KB	Output is correct