Submission #339697

#TimeUsernameProblemLanguageResultExecution timeMemory
339697couplefireMatch (CEOI16_match)C++17
100 / 100
20 ms12160 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

int n; string s;
string ans;
int dp[MAXN][26];

bool solve(int l, int r){
    if(l == r+1) return 1;
    if(dp[r][s[l]-'a'] < l) return false;
    ans[l] = '(', ans[dp[r][s[l]-'a']-1] = ')';
    return solve(l+1, dp[r][s[l]-'a']-2) && solve(dp[r][s[l]-'a'], r);
}

int main(){
    // freopen("match.in", "r", stdin);
    // freopen("match.out", "w", stdout);
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...