oj.uz

Submission #134361

# Submission time Handle Problem Language Result Execution time Memory
134361 2019-07-22T13:44:30 Z imyujin Match (CEOI16_match) C++14
0 / 100
 58 ms 61352 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);
		}
		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);
		}
	}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 61352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 61352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 61352 KB Output isn't correct
2 Halted 0 ms 0 KB -