제출 #566937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566937		piOOE	Match (CEOI16_match)	C++17	37 / 100	2095 ms	828 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();
    };
    if (!check(s, ans)) {
        cout << -1;
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        ans[i] = '(';
        if (check(s, ans)) continue;
        ans[i] = ')';
    }
    cout << ans;
    return 0;
}

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