Submission #566922

#	Time	Username	Problem	Language	Result	Execution time	Memory
566922		piOOE	Match (CEOI16_match)	C++17	37 / 100	2074 ms	1060 KiB

match

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = sz(s);
    string ans;
    ans.resize(n, '?');
    auto check = [](string s, string ans) {
        int n = sz(s);
        vector<int> st;
        for (int i = 0; i < n; ++i) {
            if (ans[i] == '?') {
                if (st.empty()) {
                    st.push_back(i);
                } else {
                    if (s[st.back()] == s[i]) {
                        st.pop_back();
                    } else {
                        st.push_back(i);
                    }
                }
            } else if (ans[i] == '('){
                st.push_back(i);
            } else {
                if (st.empty() || s[st.back()] != s[i]) {
                    return false;
                }
                st.pop_back();
            }
        }
        return st.empty();
    };
    for (int i = 0; i < n; ++i) {
        ans[i] = '(';
        if (check(s, ans)) continue;
        ans[i] = ')';
        if (!check(s, ans)) {
            cout << -1;
            return 0;
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63