oj.uz

Submission #37352

# Submission time Handle Problem Language Result Execution time Memory
37352 2017-12-24T14:43:36 Z cheater2k Match (CEOI16_match) C++14
37 / 100
 13 ms 16880 KB 
#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() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> s, n = s.size();

	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 16728 KB Output is correct
2 Correct 0 ms 16728 KB Output is correct
3 Correct 0 ms 16728 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16728 KB Output is correct
2 Correct 0 ms 16728 KB Output is correct
3 Correct 0 ms 16728 KB Output is correct
4 Correct 0 ms 16728 KB Output is correct
5 Correct 0 ms 16728 KB Output is correct
6 Correct 0 ms 16728 KB Output is correct
7 Correct 0 ms 16728 KB Output is correct
8 Correct 3 ms 16728 KB Output is correct
9 Correct 0 ms 16728 KB Output is correct
10 Correct 0 ms 16728 KB Output is correct
11 Correct 3 ms 16728 KB Output is correct
12 Runtime error 13 ms 16880 KB Execution killed because of forbidden syscall writev (20)
13 Halted 0 ms 0 KB -