Submission #605993

#	Time	Username	Problem	Language	Result	Execution time	Memory
605993		maximath_1	Match (CEOI16_match)	C++11	100 / 100	18 ms	13600 KiB

match

#include <bits/stdc++.h>
using namespace std;
 
const int MX = 2e5 + 5;
int pre[MX][30];
string s, ans; int n;
 
void solve(int l, int r){
	if(l > r) return;
	if(pre[r][s[l] - 'a'] <= l){
		cout << -1 << endl;
		exit(0);
	}
 
	ans[l] = '(';
	ans[pre[r][s[l] - 'a']] = ')';
	solve(l + 1, pre[r][s[l] - 'a'] - 1);
	solve(pre[r][s[l] - 'a'] + 1, r);
}
 
int main(){
	cin >> s;
	n = s.size(); ans = "";
	for(int i = 0; i < n; i ++){
		ans += '(';
		for(int j = 0; j < 26; j ++){
			if(j == s[i] - 'a') pre[i][j] = i;
			else if(i > 0 && pre[i - 1][s[i] - 'a'] > 0)
				pre[i][j] = pre[pre[i - 1][s[i] - 'a'] - 1][j];
			else pre[i][j] = -1;
		}
	}
	solve(0, n - 1);
	cout << ans << endl;
}

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