oj.uz

Submission #57184

# Submission time Handle Problem Language Result Execution time Memory
57184 2018-07-14T08:43:07 Z Bruteforceman Match (CEOI16_match) C++11
100 / 100
 44 ms 33428 KB 
#include <bits/stdc++.h>
using namespace std;
string s;
bool decide[100010];
int dp[26][100010];
int node[26][100010];
int par[100010];
char letter[100010];
int alpha[26][100010];
char ans[100010];

void solve(int l, int r) {
	if(l > r) {
		return ;
	}
	int opt = dp[s[l] - 'a'][r];
	if(opt <= l) {
		cout << -1 << endl;
		exit(0);
	}
	ans[l] = '(';
	ans[opt] = ')';
	solve(l + 1, opt - 1);
	solve(opt + 1, r);
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie();
	cin >> s;
	int n = s.size();
	letter[0] = '#';
	int cur = 0;
	int idx = 0;
	memset(node, -1, sizeof node);
	memset(alpha, -1, sizeof alpha);

	for(int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		if(letter[cur] == s[i]) {
			cur = par[cur];
		} else {
			int nxt;
			if(node[c][cur] == -1) nxt = ++idx;
			else nxt = node[c][cur];
			node[c][cur] = nxt;
			par[nxt] = cur;
			letter[nxt] = s[i];
			cur = nxt;
		}
		alpha[c][cur] = i;
		for(int j = 0; j < 26; j++) {
			dp[j][i] = alpha[j][cur];
		}
	}
	solve(0, n-1);
	for(int i = 0; i < n; i++) {
		cout << ans[i];
	}
	cout << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 20856 KB Output is correct
2 Correct 19 ms 20856 KB Output is correct
3 Correct 18 ms 20960 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 20856 KB Output is correct
2 Correct 19 ms 20856 KB Output is correct
3 Correct 18 ms 20960 KB Output is correct
4 Correct 19 ms 21120 KB Output is correct
5 Correct 18 ms 21176 KB Output is correct
6 Correct 19 ms 21228 KB Output is correct
7 Correct 19 ms 21228 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 20856 KB Output is correct
2 Correct 19 ms 20856 KB Output is correct
3 Correct 18 ms 20960 KB Output is correct
4 Correct 19 ms 21120 KB Output is correct
5 Correct 18 ms 21176 KB Output is correct
6 Correct 19 ms 21228 KB Output is correct
7 Correct 19 ms 21228 KB Output is correct
8 Correct 23 ms 21744 KB Output is correct
9 Correct 21 ms 21880 KB Output is correct
10 Correct 24 ms 21904 KB Output is correct
11 Correct 19 ms 21952 KB Output is correct
12 Correct 34 ms 28108 KB Output is correct
13 Correct 40 ms 28804 KB Output is correct
14 Correct 43 ms 29780 KB Output is correct
15 Correct 32 ms 30876 KB Output is correct
16 Correct 36 ms 31084 KB Output is correct
17 Correct 42 ms 31692 KB Output is correct
18 Correct 40 ms 31692 KB Output is correct
19 Correct 44 ms 32704 KB Output is correct
20 Correct 40 ms 32704 KB Output is correct
21 Correct 39 ms 33428 KB Output is correct