oj.uz

Submission #955018

# Submission time Handle Problem Language Result Execution time Memory
955018 2024-03-29T07:47:04 Z parlimoos Match (CEOI16_match) C++14
10 / 100
 841 ms 524288 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , blks[100000] , rs[100000];
vector<int> s;
string o;
vector<int> sqs[100000][26];
bool iso = 1;
int infs[100000][26];

void init(){
    fill(&infs[0][0] , &infs[n - 1][26] , n) , fill(&rs[0] , &rs[n] , -1);
    blks[n - 1] = n , infs[n - 1][s[n - 1]] = n - 1;
    for(int i = n - 2 ; i >= 0 ; i--){
        blks[i] = infs[i + 1][s[i]];
        for(int c = 0 ; c < 26 ; c++){
            if(blks[i] != n) infs[i][c] = infs[blks[i] + 1][c];
            else infs[i][c] = n;
        }
        infs[i][s[i]] = i;
    }
    int cnt = 0;
    for(int i = 0 ; i < n ; i++){
        if(rs[i] != -1) continue;
        for(int j = i ; j < n ; j = blks[j] + 1){
            rs[j] = cnt , sqs[cnt][s[j]].pb(j);
        }
        cnt++;
    }
    // for(int i = 0 ; i < n ; i++) cout << i << " " << blks[i] << "!!\n";
}
int getBst(int l , int r){
    int inx = rs[l + 1];
    auto itr = ub(sqs[inx][s[l]].bg() , sqs[inx][s[l]].end() , r);
    if(itr == sqs[inx][s[l]].bg()) return -1;
    if(*(--itr) <= l) return -1;
    return *(itr);
}
void f(int l = 0 , int r = n - 1){
    if(l > r) return;
    int inx = getBst(l , r);
    if(inx == -1){
        iso = 0;
        return;
    }
    o[l] = '(' , o[inx] = ')';
    f(l + 1 , inx - 1) , f(inx + 1 , r);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    string d;
    cin >> d;
    n = (int)d.length() , o = d;
    for(char c : d) s.pb(int(c - 'a'));
    init() , f();
    if(!iso) cout << -1;
    else cout << o;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63828 KB Output is correct
2 Correct 19 ms 63836 KB Output is correct
3 Correct 19 ms 63832 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63828 KB Output is correct
2 Correct 19 ms 63836 KB Output is correct
3 Correct 19 ms 63832 KB Output is correct
4 Runtime error 841 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63828 KB Output is correct
2 Correct 19 ms 63836 KB Output is correct
3 Correct 19 ms 63832 KB Output is correct
4 Runtime error 841 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -