Submission #608507

#	Time	Username	Problem	Language	Result	Execution time	Memory
608507		SeDunion	Match (CEOI16_match)	C++17	100 / 100	706 ms	10960 KiB

match

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63