oj.uz

답안 #740994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740994 2023-05-13T11:12:18 Z 이동현(#9959) 괄호 문자열 (CEOI16_match) C++17
0 / 100
 91 ms 235084 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int NS = (int)1e5 + 4;
string s;
int n;
int spa[NS][30][20];

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

    cin >> s;
    n = (int)s.size();
    memset(spa, -1, sizeof(spa));
    for(int i = n - 3; i >= 0; --i){
        if(s[i] == s[i + 1]){
            spa[i][s[i + 2] - 'a'][0] = i + 1;
            continue;
        }
        int p = spa[i + 1][s[i] - 'a'][0];
        if(p != -1 && p + 2 < n){
            spa[i][s[p + 2] - 'a'][0] = p + 1;
        }
    }
    for(int j = 0; j < 26; ++j){
        for(int k = 1; k < 20; ++k){
            for(int i = 0; i < n; ++i){
                spa[i][j][k] = (spa[i][j][k - 1] == -1 ? -1 : spa[spa[i][j][k - 1] + 1][j][k - 1]);
            }
        }
    }

    string ans(n, '$');
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 0; i < n; ++i){
        if(!pq.empty() && pq.top() <= i){
            pq.pop();
            continue;
        }

        int lim = n + 243;
        if(!pq.empty()) lim = pq.top();
        int now = i + 1;
        for(int k = 19; k >= 0; --k){
            if(spa[now][s[i] - 'a'][k] != -1 && spa[now][s[i] - 'a'][k] + 1 < lim){
                now = spa[now][s[i] - 'a'][k];
            }
        }

        ++now;
        if(s[i] == s[i + 1]) now = i + 1;
        if(now >= lim){
            cout << "-1\n";
            return 0;
        }

        ans[i] = '(';
        ans[now] = ')';
        pq.push(now);
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 235084 KB Output is correct
2 Incorrect 85 ms 235048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 235084 KB Output is correct
2 Incorrect 85 ms 235048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 235084 KB Output is correct
2 Incorrect 85 ms 235048 KB Output isn't correct
3 Halted 0 ms 0 KB -