Submission #339698

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
3396982020-12-26 00:04:19couplefireMatch (CEOI16_match)C++17
100 / 100
18 ms12012 KiB
#include <bits/stdc++.h>
using namespace std;
int n; string s; string ans;
int dp[100005][26];
bool solve(int l, int r){
if(l == r+1) return 1;
if(dp[r][s[l]-'a'] < l) return false;
int a = dp[r][s[l]-'a'];
ans[l] = '(', ans[a-1] = ')';
return solve(l+1, a-2) && solve(a, r);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> s; n = s.length(); ans.resize(n);
for(int i = 0; i<n; i++){
for(int j = 0; j<26; j++){
dp[i][j] = -1;
if(s[i]-'a' == j) dp[i][j] = i+1;
if(i >= 1 && dp[i-1][s[i]-'a']-2 >= 0) dp[i][j] = max(dp[i][j], dp[dp[i-1][s[i]-'a']-2][j]);
}
}
if(!solve(0, n-1)) cout << -1 << endl;
else cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...