제출 #605993

#제출 시각아이디문제언어결과실행 시간메모리
605993maximath_1괄호 문자열 (CEOI16_match)C++11
100 / 100
18 ms13600 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...