oj.uz

Submission #1118024

# Submission time Handle Problem Language Result Execution time Memory
1118024 2024-11-24T17:58:33 Z vjudge1 Match (CEOI16_match) C++17
37 / 100
 391 ms 524288 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(sz, 'a');

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

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

    rec(1, n, s);

    // cout << "n" << endl;

    if(ok == false ) {
        cout << -1 << endl;
    } else  {
        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:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 3 ms 3664 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 5 ms 4512 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 3 ms 3664 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 5 ms 4512 KB Output is correct
8 Correct 9 ms 6036 KB Output is correct
9 Correct 29 ms 19056 KB Output is correct
10 Correct 35 ms 16024 KB Output is correct
11 Correct 45 ms 26084 KB Output is correct
12 Runtime error 391 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -