Submission #845416

#TimeUsernameProblemLanguageResultExecution timeMemory
8454161binMatch (CEOI16_match)C++14
100 / 100
9 ms12712 KiB
#include<bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, a[NMAX], dp[NMAX][26], ans[NMAX];
string s;

int go(int l, int r){
	if(l > r) return 1;
	int x = dp[r][a[l]];
	if(x <= l) return 0;

	ans[l] = 1; ans[r] = -1;
	return go(l + 1, x - 1) && go(x + 1, r);
}

int main(void){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;
	n = s.size();
	for(int i = 1; i <= n; i++) a[i] = s[i - 1] - 'a';
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 26; j++){
			if(a[i] == j) dp[i][j] = i;
			else if(dp[i - 1][a[i]] >= 1) dp[i][j] = dp[dp[i - 1][a[i]] - 1][j];
		}
	if(!go(1, n)) cout << -1;
	else{
		for(int i = 1; i <= n; i++) cout << (ans[i] == 1 ? '(' : ')');
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...