oj.uz

Submission #134370

# Submission time Handle Problem Language Result Execution time Memory
134370 2019-07-22T13:51:34 Z imyujin Match (CEOI16_match) C++14
100 / 100
 95 ms 69712 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

char s[MAXN];
int par[MAXN], chi[MAXN][26], non;
vector<int> idx[MAXN][26];
int no[MAXN];
char ans[MAXN];

bool solve(int l, int r) {
	if(l > r) return true;
	vector<int> &v = idx[no[l - 1]][s[l] - 'a'];
	int k = upper_bound(v.begin(), v.end(), r) - v.begin();
	if(k == 0 || v[k - 1] <= l) return false;
	ans[l] = '(';
	ans[v[k - 1]] = ')';
	return solve(l + 1, v[k - 1] - 1) && solve(v[k - 1] + 1, r);
}

int main() {
	int N;

	cin >> (s + 1);

	for(N = 1; s[N]; N++);
	N--;

	stack<int> st;
	par[0] = -1;
	for(int i = 0; i < 26; i++) chi[0][i] = -1;
	no[0] = 0;
	non = 1;
	for(int i = 1; i <= N; i++) {
		if(!st.empty() && st.top() == s[i]) {
			no[i] = par[no[i - 1]];
			idx[no[i]][s[i] - 'a'].push_back(i);
			st.pop();
		}
		else {
			if(chi[no[i - 1]][s[i] - 'a'] == -1) {
				par[non] = no[i - 1];
				for(int j = 0; j < 26; j++) chi[non][j] = -1;
				chi[no[i - 1]][s[i] - 'a'] = non++;
			}
			no[i] = chi[no[i -1]][s[i] - 'a'];
			idx[no[i]][s[i] - 'a'].push_back(i);
			st.push(s[i]);
		}
	}

	if(solve(1, N)) for(int i = 1; i <= N; i++) cout << ans[i];
	else cout << -1;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 61432 KB Output is correct
2 Correct 57 ms 61432 KB Output is correct
3 Correct 56 ms 61432 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 61432 KB Output is correct
2 Correct 57 ms 61432 KB Output is correct
3 Correct 56 ms 61432 KB Output is correct
4 Correct 59 ms 61432 KB Output is correct
5 Correct 58 ms 61432 KB Output is correct
6 Correct 58 ms 61504 KB Output is correct
7 Correct 57 ms 61420 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 61432 KB Output is correct
2 Correct 57 ms 61432 KB Output is correct
3 Correct 56 ms 61432 KB Output is correct
4 Correct 59 ms 61432 KB Output is correct
5 Correct 58 ms 61432 KB Output is correct
6 Correct 58 ms 61504 KB Output is correct
7 Correct 57 ms 61420 KB Output is correct
8 Correct 59 ms 61816 KB Output is correct
9 Correct 60 ms 61944 KB Output is correct
10 Correct 60 ms 62048 KB Output is correct
11 Correct 61 ms 62328 KB Output is correct
12 Correct 81 ms 67192 KB Output is correct
13 Correct 81 ms 67704 KB Output is correct
14 Correct 83 ms 68108 KB Output is correct
15 Correct 71 ms 63480 KB Output is correct
16 Correct 71 ms 63480 KB Output is correct
17 Correct 83 ms 66680 KB Output is correct
18 Correct 73 ms 63068 KB Output is correct
19 Correct 92 ms 69712 KB Output is correct
20 Correct 77 ms 67320 KB Output is correct
21 Correct 95 ms 69684 KB Output is correct