oj.uz

답안 #1118023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1118023 2024-11-24T17:57:47 Z vjudge1 괄호 문자열 (CEOI16_match) C++17
37 / 100
 381 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 = 1e5 + 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 736 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 4 ms 1872 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 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 736 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 4 ms 1872 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 8 ms 3220 KB Output is correct
9 Correct 25 ms 16084 KB Output is correct
10 Correct 42 ms 13164 KB Output is correct
11 Correct 40 ms 23348 KB Output is correct
12 Runtime error 381 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -