oj.uz

Submission #608786

# Submission time Handle Problem Language Result Execution time Memory
608786 2022-07-27T10:10:16 Z faruk Match (CEOI16_match) C++17
37 / 100
 2000 ms 960 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double

using namespace std;


int n; string s;
bool possible(stack<char> open, int idx) {
    for (int i = idx; i < n; i++) {
        if (!open.empty() && open.top() == s[i])
            open.pop();
        else
            open.push(s[i]);
    }
    return open.empty();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("match.in", "r", stdin);
    //freopen("match.out", "w", stdout);

    cin >> s;
    n = s.size();
    if (!possible(stack<char>(), 0)) {
        cout << "-1\n";
        return 0;
    }

    vector<vector<int> > where(26);
    for (int i = 0; i < n; i++) {
        where[s[i] - 'a'].push_back(i);
    }

    string out = "";
    stack<char> open;
    for (int i = 0; i < n; i++) {
        if (!open.empty() && s[i] == open.top()) {
            open.push(s[i]);
            if (possible(open, i + 1))
                out += '(';
            else
                out += ')', open.pop(), open.pop();
        }
        else
            open.push(s[i]), out += '(';
    }

    cout << out << "\n";
}

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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 55 ms 364 KB Output is correct
9 Correct 49 ms 392 KB Output is correct
10 Correct 42 ms 384 KB Output is correct
11 Correct 30 ms 404 KB Output is correct
12 Execution timed out 2085 ms 960 KB Time limit exceeded
13 Halted 0 ms 0 KB -