oj.uz

Submission #566937

# Submission time Handle Problem Language Result Execution time Memory
566937 2022-05-23T06:36:20 Z piOOE Match (CEOI16_match) C++17
37 / 100
 2000 ms 828 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, '?');
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 9 ms 336 KB Output is correct
7 Correct 17 ms 332 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 9 ms 336 KB Output is correct
7 Correct 17 ms 332 KB Output is correct
8 Correct 192 ms 340 KB Output is correct
9 Correct 226 ms 356 KB Output is correct
10 Correct 196 ms 360 KB Output is correct
11 Correct 174 ms 460 KB Output is correct
12 Execution timed out 2095 ms 828 KB Time limit exceeded
13 Halted 0 ms 0 KB -