oj.uz

Submission #539031

# Submission time Handle Problem Language Result Execution time Memory
539031 2022-03-18T09:59:33 Z alextodoran Match (CEOI16_match) C++17
100 / 100
 16 ms 12616 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = (int) 1e5;

string S;
int N;

int maxStart[N_MAX][26];

bool exists () {
    vector <int> st;
    for (int i = 0; i < N; i++) {
        if (st.empty() == true || S[st.back()] != S[i]) {
            st.push_back(i);
        } else {
            st.pop_back();
        }
    }
    return (st.empty() == true);
}

void precalc () {
    for (int i = 0; i < (int) S.size(); i++) {
        fill(maxStart[i], maxStart[i] + 26, -1);
        maxStart[i][(char) (S[i] - 'a')] = i;
    }
    for (int i = 1; i < (int) S.size(); i++) {
        for (int c = 0; c < 26; c++) {
            int j = maxStart[i - 1][S[i] - 'a'] - 1;
            if (maxStart[i][c] == -1 && j >= 0) {
                if (S[j] == (char) ('a' + c)) {
                    maxStart[i][c] = j;
                } else {
                    maxStart[i][c] = maxStart[j][c];
                }
            }
        }
    }
}

string P;
void solve (int l, int r) {
    if (l <= r) {
        int matchl = maxStart[r][S[l] - 'a'];
        P[l] = '('; P[matchl] = ')';
        solve(l + 1, matchl - 1);
        solve(matchl + 1, r);
    }
}
void solve () {
    for (int i = 0; i < N; i++) {
        P += '?';
    }
    solve(0, N - 1);
}

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

    cin >> S; N = (int) S.size();
    if (exists() == true) {
        precalc();
        solve();
        cout << P << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

Compilation message

match.cpp: In function 'void precalc()':
match.cpp:37:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         maxStart[i][(char) (S[i] - 'a')] = i;
      |                     ^~~~~~~~~~~~~~~~~~~

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 1 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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #3
63.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 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 8 ms 7632 KB Output is correct
13 Correct 8 ms 8408 KB Output is correct
14 Correct 10 ms 9260 KB Output is correct
15 Correct 11 ms 10836 KB Output is correct
16 Correct 11 ms 10920 KB Output is correct
17 Correct 13 ms 11408 KB Output is correct
18 Correct 15 ms 10708 KB Output is correct
19 Correct 16 ms 11684 KB Output is correct
20 Correct 10 ms 7948 KB Output is correct
21 Correct 15 ms 12616 KB Output is correct