Submission #339695

#TimeUsernameProblemLanguageResultExecution timeMemory
339695couplefire괄호 문자열 (CEOI16_match)C++17
37 / 100
2084 ms19180 KiB
#include <bits/stdc++.h>
using namespace std;

int n; string s;
string ans;

bool solve(int l, int r){
    if(l == r+1) return 1;
    if(s[l] == s[r]){
        ans[l] = '('; ans[r] = ')';
        return solve(l+1, r-1);
    }
    stack<int> st; int good = -1;
    for(int i = l; i<=r; i++){
        if(!st.empty() && st.top() == s[i]-'a') st.pop();
        else st.push(s[i]-'a');
        if(st.empty() && s[i] == s[l]) good = i;
    }
    if(good == -1) return false;
    ans[l] = '('; ans[good] = ')';
    return solve(l+1, good-1)&&solve(good+1, 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);
    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...