제출 #608500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608500		SeDunion	괄호 문자열 (CEOI16_match)	C++17	37 / 100	977 ms	20068 KiB

match

#include<iostream>
#include<assert.h>
#include<vector>
#include<string>


using namespace std;

int n;
string s, ans;

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 (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;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63