oj.uz

Submission #608504

# Submission time Handle Problem Language Result Execution time Memory
608504 2022-07-27T08:02:35 Z SeDunion Match (CEOI16_match) C++17
37 / 100
 2000 ms 12628 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 dp[N][N];
int us[N][N];

int solve(int l, int r) {
	if (l > r) return 1;
	if (us[l][r]) return dp[l][r];
	us[l][r] = 1;
	for (int i = r ; i > l ; i -= 2) {
		if (s[i] == s[l] && solve(l+1, i-1) && solve(i + 1, r)) {
			return dp[l][r] = 1;
		}
	}
	return dp[l][r];
}
*/
int L[N][26], R[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;
			R[i][c] = -1;
		}
	}
	for (int i = n-1 ; i >= 0 ; -- i) {
		R[i][s[i]-'a']=i;
		if (i+2<n && s[i + 1] == s[i]) {
			R[i][s[i+2]-'a'] = i+2;
		}
		for (int rep = 0 ; rep < 26 ; ++ rep) {
			for (int a = 0 ; a < 26 ; ++ a) {
				for (int b = 0 ; b < 26 ; ++ b) {
					if (R[i][b] != -1)
						R[i][a] = max(R[i][a], R[R[i][b]][a]);
				}
			}
		}
	}
	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'];
			cerr << j << " -> " << i << endl;
			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 < 100 ; ++ 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;
	}
	/*cerr << endl;
	for (int i = 0 ; i < n ; ++ i) {
		for (int j = 0 ; j < 26 ; ++ j) {
			if (R[i][j] == -1) cerr << "- ";
			else cerr << R[i][j] << " ";
		}
		cerr << endl;
	}*/
	/*if (!solve(0, n-1)) {
		cout << -1;
		return 0;
	}*/
	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:111:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  111 |    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 2 ms 212 KB Output is correct
3 Correct 2 ms 340 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 2 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 106 ms 508 KB Output is correct
5 Correct 112 ms 520 KB Output is correct
6 Correct 155 ms 616 KB Output is correct
7 Correct 207 ms 728 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 106 ms 508 KB Output is correct
5 Correct 112 ms 520 KB Output is correct
6 Correct 155 ms 616 KB Output is correct
7 Correct 207 ms 728 KB Output is correct
8 Correct 739 ms 1656 KB Output is correct
9 Correct 845 ms 1760 KB Output is correct
10 Correct 879 ms 1756 KB Output is correct
11 Correct 828 ms 1764 KB Output is correct
12 Execution timed out 2091 ms 12628 KB Time limit exceeded
13 Halted 0 ms 0 KB -