oj.uz

답안 #1117661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117661 2024-11-24T07:14:42 Z vjudge1 괄호 문자열 (CEOI16_match) C++17
10 / 100
 100 ms 7504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N;
    string S;
    cin >> S;
    S = '-' + S;
    N = S.size();
    if (N % 2 == 0) {
        cout << "-1\n";
        return 0;
    }
    vector<vector<set<int>>> ind(26, vector<set<int>>(2));
    for (int i = 1;i < N;i ++) {
        ind[S[i] - 'a'][i % 2].insert(i);
    }
    vector<vector<int>> dp(N + 1, vector<int> (N + 1, 0));
    vector<vector<int>> go(N + 1, vector<int> (N + 1, 0));
    for (int i = 1;i <= N;i ++) {
        for (int j = 1;j < i;j ++) {
            dp[i][j] = 1;
        }
    }
    for (int len = 2;len < N;len += 2) {
        for (int l = 1, r = len;r < N;r ++, l ++) {
            if (S[l] == S[r] && dp[l + 1][r - 1] == 1) {
                dp[l][r] = 1;
                go[l][r] = -1;
            } else {
                auto _r = ind[S[l] - 'a'][1 - l % 2].lower_bound(r);
                while (_r != ind[S[l] - 'a'][1 - l % 2].begin()) {
                    // cerr << "while _r != ind[S[l] - 'a'][l % 2].begin()\n";
                    _r = prev(_r);
                    // if (l == 2 && r == 5) {
                    //     cout << *_r << " " << dp[l + 1][*_r - 1] << " " << dp[*_r + 1][r] << "\n";
                    // }
                    if (dp[l][*_r] == 1 && S[*_r + 1] == S[r] && dp[*_r + 1][r] == 1) {
                        dp[l][r] = 1;
                        go[l][r] = *_r;
                        break;
                    }
                }
            }
        }
    }
    // for (int i = 1;i < N;i ++) {
    //     for (int j = i;j < N;j ++) {
    //         cout << dp[i][j] << " ";
    //     } cout << "\n";
    // }
    if (dp[1][N - 1] == 0) {
        cout << "-1\n";
        return 0;
    }
    string ans(N, ' ');
    function<void(int, int)> get_answer = [&](int l, int r) -> void {
        if (l > r || l <= 0 || l > N - 1 || r <= 0 || r > N - 1) return;
        if (go[l][r] == -1) {
            ans[l - 1] = '(';
            ans[r - 1] = ')';
            get_answer (l + 1, r - 1);
        } else {
            ans[l - 1] = '(';
            ans[go[l][r] - 1] = ')';
            ans[go[l][r]] = '(';
            ans[r - 1] = ')';
            get_answer (l + 1, go[l][r] - 1);
            get_answer (go[l][r] + 2, r - 1);
        }
    };
    get_answer (1, N - 1);
    cout << ans << "\n";
}

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
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 Incorrect 100 ms 7504 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 Incorrect 100 ms 7504 KB Output isn't correct
5 Halted 0 ms 0 KB -