oj.uz

Submission #1118026

# Submission time Handle Problem Language Result Execution time Memory
1118026 2024-11-24T18:05:35 Z vjudge1 Match (CEOI16_match) C++17
100 / 100
 24 ms 23640 KB 
#include <bits/stdc++.h>
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define ALL(x) x.begin(), x.end()
#define intt long long
#define pb push_back
#define endl "\n"

const int sz = 3e6 + 5, L = 20;
intt dp[sz][27];
bool valid(string& s) {
    stack<char>st;
    for(int i = 0; i < s.size(); i++) {
        if(!st.empty() && st.top() == s[i]) {
            st.pop();
        } else{
            st.push(s[i]);
        }
    }
    return st.empty();
}

string ans, s;

void rec(intt l, intt r) {
    if(l < r) {
        intt pos = dp[r][s[l] - 'a'];
        ans[l - 1] = '(';
        ans[pos - 1] = ')';
        rec(l + 1, pos - 1);
        rec(pos + 1, r);
    }
}

void solve() {
    cin >> s;
    int n = s.size();
    if(!valid(s)) {
        cout << -1 << endl;
        return;
    }
    ans.resize(n);
    s = '?' + s;
    bool ok = true;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 26; j++) {
            if(s[i] == char('a' + j)) {
                dp[i][j] = i;
            } else {
                int last = dp[i-1][s[i]-'a'];
                if(last > 0) {
                    dp[i][j] = dp[last-1][j];
                }
            }
        }
    }
    rec(1, n);
    cout << ans << endl;
}

int main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

Compilation message

match.cpp: In function 'bool valid(std::string&)':
match.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
match.cpp: In function 'void solve()':
match.cpp:45:10: warning: unused variable 'ok' [-Wunused-variable]
   45 |     bool ok = true;
      |          ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 1020 KB Output is correct
7 Correct 2 ms 848 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 1020 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 1872 KB Output is correct
9 Correct 2 ms 1872 KB Output is correct
10 Correct 2 ms 2140 KB Output is correct
11 Correct 3 ms 2028 KB Output is correct
12 Correct 14 ms 14464 KB Output is correct
13 Correct 15 ms 15440 KB Output is correct
14 Correct 17 ms 16976 KB Output is correct
15 Correct 19 ms 19792 KB Output is correct
16 Correct 20 ms 19596 KB Output is correct
17 Correct 22 ms 20984 KB Output is correct
18 Correct 19 ms 20556 KB Output is correct
19 Correct 24 ms 22096 KB Output is correct
20 Correct 16 ms 14672 KB Output is correct
21 Correct 24 ms 23640 KB Output is correct