oj.uz

Submission #128033

# Submission time Handle Problem Language Result Execution time Memory
128033 2019-07-10T10:44:01 Z PeppaPig Match (CEOI16_match) C++14
10 / 100
 59 ms 61432 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n, dep[N];
char a[N], ans[N];
stack<int> S;
vector<int> id[N][26];

void solve(int l, int r) {
    if(l > r) return;
    vector<int> &v = id[dep[l]][a[l] - 'a'];
    auto it = --lower_bound(v.begin(), v.end(), r + 1);
    ans[l] = '(', ans[*it] = ')';
    solve(l + 1, *it - 1), solve(*it + 1, r);
}

int main() {
    scanf("%s", a + 1);
    n = strlen(a + 1);

    for(int i = 1; i <= n; i++) {
        if(S.empty() || a[S.top()] != a[i]) {
            dep[i] = S.size() + 1;
            S.emplace(i);
        } else {
            dep[i] = dep[S.top()];
            S.pop();
        }
    }
    for(int i = 1; i <= n; i++) id[dep[i]][a[i] - 'a'].emplace_back(i);
    if(S.size()) return !printf("-1\n");
    else solve(1, n);

    printf("%s\n", ans + 1);

    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", a + 1);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 61432 KB Output is correct
2 Correct 59 ms 61432 KB Output is correct
3 Correct 58 ms 61432 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 61432 KB Output is correct
2 Correct 59 ms 61432 KB Output is correct
3 Correct 58 ms 61432 KB Output is correct
4 Incorrect 58 ms 61432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 61432 KB Output is correct
2 Correct 59 ms 61432 KB Output is correct
3 Correct 58 ms 61432 KB Output is correct
4 Incorrect 58 ms 61432 KB Output isn't correct
5 Halted 0 ms 0 KB -