oj.uz

Submission #741001

# Submission time Handle Problem Language Result Execution time Memory
741001 2023-05-13T11:27:08 Z 이동현(#9959) Match (CEOI16_match) C++17
0 / 100
 86 ms 235144 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){
        int v = -1;
        if(s[i] == s[i + 1]){
            v = spa[i][s[i + 2] - 'a'][0] = i + 1;
        }
        else{
            int p = spa[i + 1][s[i] - 'a'][0];
            if(p != -1 && p + 2 < n){
                v = spa[i][s[p + 2] - 'a'][0] = p + 1;
            }
        }
        for(int j = 0; j < 26; ++j){
            if(v != -1 && spa[i][j][0] == -1){
                spa[i][j][0] = spa[v + 1][j][0];
            }
        }
    }
    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] + 1;
            }
        }

        if(s[i] == s[i + 1] && (now >= lim || s[i] != s[now])) 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

# Verdict Execution time Memory Grader output
1 Correct 84 ms 235040 KB Output is correct
2 Correct 84 ms 235108 KB Output is correct
3 Incorrect 86 ms 235144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 235040 KB Output is correct
2 Correct 84 ms 235108 KB Output is correct
3 Incorrect 86 ms 235144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 235040 KB Output is correct
2 Correct 84 ms 235108 KB Output is correct
3 Incorrect 86 ms 235144 KB Output isn't correct
4 Halted 0 ms 0 KB -