oj.uz

Submission #608495

# Submission time Handle Problem Language Result Execution time Memory
608495 2022-07-27T08:00:27 Z SeDunion Match (CEOI16_match) C++17
10 / 100
 72 ms 13976 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 = 2022;
 
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 (l + 1 == r) {
		ans[l] = '(';
		ans[r] = ')';
		return;
	}
	int i = L[r][s[l]-'a'];
	cerr << l << " " << r << " " << i << endl;
	if (i != -1) {
		ans[l] = '(';
		ans[i] = ')';
		get(l+1,i-1);
		get(i+1,r);
		return;
	}
	i = R[l][s[r]-'a'];
	if (i != -1) {
		ans[i] = '(';
		ans[r] = ')';
		get(l,i-1);
		get(i+1,r-1);
		return;
	}
	//while(1);
	/*
	for (int i = r ; i > l ; i -= 2) {
		if (s[i] == s[l] && solve(i + 1, r)) {
			assert(solve(l+1,i-1));
		//if (s[i] == s[l] && solve(l+1, i-1) && solve(i + 1, r)) {
			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;
		}
		L[i][s[i]-'a']=i;
		for (int rep = 0 ; rep < 26 ; ++ rep) {
			for (int a = 0 ; a < 26 ; ++ a) {
				for (int b = 0 ; b < 26 ; ++ b) {
					if (L[i][b] >= 0)
						L[i][a] = max(L[i][a], L[L[i][b]][a]);
				}
			}
		}
	}
	for (int i = 0 ; i < n ; ++ 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;
	for (char i : ans) {
		assert(i == '(' || i == ')');
	}
	cout << ans;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Runtime error 72 ms 13976 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Runtime error 72 ms 13976 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -