oj.uz

Submission #567296

# Submission time Handle Problem Language Result Execution time Memory
567296 2022-05-23T10:17:43 Z piOOE Match (CEOI16_match) C++17
0 / 100
 0 ms 212 KB 
#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, '?');
    function<bool(string, string)> check = [](string s, string ans) -> bool {
        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;
    }
    vector<int> st;
    map<int, map<char, set<int>>> gs;
    vector<int> nxt(n + 1, -1), wow(n);
    map<int, int> pr;
    for (int i = 0; i < n; ++i) {
        if (st.empty()) {
            st.push_back(i);
            ans[i] = '(';
        } else {
            if (s[st.back()] == s[i]) {
                nxt[st.back()] = i;
                ans[i] = ')';
                gs[sz(st) - 1][s[i]].insert(st.back());
                wow[st.back()] = sz(st) - 1;
                st.pop_back();
            } else {
                ans[i] = '(';
                st.push_back(i);
            }
        }
    }
    int mn = n + 1;
    for (int ii = 0; ii < n; ++ii) {
        int fi = ii;
        int se = nxt[fi];
        if (se == -1 || ans[fi] == ')') continue;
        if (mn < fi) {
            mn = n + 1;
        }
        if (mn == fi) continue;
        char c = s[fi];
//        trace(c)
        auto it = gs[wow[fi]][c].lower_bound(mn);
        assert(it != gs[wow[fi]][c].begin());
        --it;
        if (*it == fi) {
            continue;
        }
        ans[fi] = '(';
        ans[se] = '(';
        ans[*it] = ')';
        ans[nxt[*it]] = ')';
        mn = *it;
        gs[wow[fi]][c].erase(it);
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -