Submission #1298218

#TimeUsernameProblemLanguageResultExecution timeMemory
1298218Cebrayil09Match (CEOI16_match)C++20
37 / 100
2091 ms1116 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0);

    string s; cin >> s;
    int n = s.size();

    if(n&1) {
        cout << "-1\n";
        return 0;
    }


    vector<char> st;
    string ans = "";

    for(int i = 0;i < n;i++) {
        if(st.size() && s[i] == st.back()) {
            st.pop_back();
            ans += ")";
        }
        else {
            st.push_back(s[i]);
            ans += "(";
        }
    }

    if(st.size()) {
        cout << "-1\n";
        return 0;
    }

    st.push_back(s[0]);
    string pref = "(";
    for(int i = 1;i < n;i++) {
        if(ans[i] == '(') {
            pref += "(";
            st.push_back(s[i]);

            continue;
        }

        string cur = pref + "(";

        vector<char> req = st;
        req.push_back(s[i]);

        for(int j = i+1;j < n;j++) {
            if(req.size() && req.back() == s[j]) {
                req.pop_back();
                cur += ")";
            }
            else {
                req.push_back(s[j]);
                cur += "(";
            }
        }

        if(req.empty()) ans = min(ans, cur);

        pref.push_back(ans[i]);
        if(ans[i] == '(') st.push_back(s[i]);
        else st.pop_back();
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...