oj.uz

Submission #608507

# Submission time Handle Problem Language Result Execution time Memory
608507 2022-07-27T08:04:15 Z SeDunion Match (CEOI16_match) C++17
100 / 100
 706 ms 10960 KB 
#include<iostream>
#include<assert.h>
#include<vector>
#include<string>


using namespace std;

int n;
string s, ans;

#define cerr if(false)cerr

const int N = 1e5 + 123;

int L[N][26];

void get(int l, int r) {
	if (l > r) return;
	if (s[l] == s[r]) {
		ans[l] = '(';
		ans[r] = ')';
		get(l+1,r-1);
		return;
	}
	int i = L[r][s[l]-'a'];
	if (i == -1) {
		cout << -1;
		exit(0);
	}
	if (i != -1) {
		ans[l] = '(';
		ans[i] = ')';
		get(l+1,i-1);
		get(i+1,r);
		return;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> s;
	n = s.size();
	for (int i = 0 ; i < n ; ++ i) cerr << i;
	cerr << endl;
	for (int i = 0 ; i < n ; ++ i) {
		for (int c = 0 ; c < 26 ; ++ c) {
			L[i][c] = -1;
		}
	}
	for (int i = 0 ; i < n ; ++ i) {
		if (i>=2 && s[i - 1] == s[i]) {
			L[i][s[i-2]-'a'] = i-2;
		}
		if (i) L[i][s[i]-'a'] = max(L[i][s[i]-'a'], L[i-1][s[i]-'a']);
		L[i][s[i]-'a']=i;
		if (i) {
			int j = L[i-1][s[i]-'a'];
			if (j > 0) {
				--j;
				for (int a = 0 ; a < 26 ; ++ a) {
					L[i][a] = max(L[i][a], L[j][a]);
				}
			}
		}
		for (int rep = 0 ; rep < 10 ; ++ rep) {
			for (int a = 0 ; a < 26 ; ++ a) {
				for (int b = 0 ; b < 26 ; ++ b) {
					int j = L[i][b];
					if (j == -1) continue;
					L[i][a] = max(L[i][a], L[j][a]);
				}
			}
		}
	}
	for (int i = 0 ; i < n ; ++ i) {
		cerr << i << " ";
		for (int j = 0 ; j < 26 ; ++ j) {
			if (L[i][j] == -1) cerr << "- ";
			else cerr << L[i][j] << " ";
		}
		cerr << endl;
	}
	ans = string(n, '-');
	get(0, n - 1);
	for (int i = 0 ; i < n ; ++ i) cerr << i;
	cerr << endl;
	cout << ans;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:79:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   79 |    if (L[i][j] == -1) cerr << "- ";
      |       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 11 ms 476 KB Output is correct
7 Correct 16 ms 536 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 11 ms 476 KB Output is correct
7 Correct 16 ms 536 KB Output is correct
8 Correct 64 ms 976 KB Output is correct
9 Correct 49 ms 1036 KB Output is correct
10 Correct 49 ms 1048 KB Output is correct
11 Correct 50 ms 1028 KB Output is correct
12 Correct 410 ms 6660 KB Output is correct
13 Correct 557 ms 7168 KB Output is correct
14 Correct 528 ms 7748 KB Output is correct
15 Correct 628 ms 8660 KB Output is correct
16 Correct 641 ms 8660 KB Output is correct
17 Correct 660 ms 9184 KB Output is correct
18 Correct 691 ms 9684 KB Output is correct
19 Correct 658 ms 10468 KB Output is correct
20 Correct 428 ms 6660 KB Output is correct
21 Correct 706 ms 10960 KB Output is correct