oj.uz

Submission #955024

# Submission time Handle Problem Language Result Execution time Memory
955024 2024-03-29T07:53:50 Z parlimoos Match (CEOI16_match) C++14
100 / 100
 36 ms 76748 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 - 1) 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++;
    }
}
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 << endl;
    else cout << o << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 63836 KB Output is correct
2 Correct 18 ms 63836 KB Output is correct
3 Correct 18 ms 63836 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 63836 KB Output is correct
2 Correct 18 ms 63836 KB Output is correct
3 Correct 18 ms 63836 KB Output is correct
4 Correct 18 ms 64092 KB Output is correct
5 Correct 19 ms 64216 KB Output is correct
6 Correct 19 ms 64092 KB Output is correct
7 Correct 19 ms 66140 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 63836 KB Output is correct
2 Correct 18 ms 63836 KB Output is correct
3 Correct 18 ms 63836 KB Output is correct
4 Correct 18 ms 64092 KB Output is correct
5 Correct 19 ms 64216 KB Output is correct
6 Correct 19 ms 64092 KB Output is correct
7 Correct 19 ms 66140 KB Output is correct
8 Correct 21 ms 66392 KB Output is correct
9 Correct 19 ms 66396 KB Output is correct
10 Correct 20 ms 66396 KB Output is correct
11 Correct 21 ms 66652 KB Output is correct
12 Correct 30 ms 73200 KB Output is correct
13 Correct 29 ms 75508 KB Output is correct
14 Correct 32 ms 75988 KB Output is correct
15 Correct 25 ms 74964 KB Output is correct
16 Correct 25 ms 74956 KB Output is correct
17 Correct 29 ms 75988 KB Output is correct
18 Correct 25 ms 74196 KB Output is correct
19 Correct 36 ms 76592 KB Output is correct
20 Correct 28 ms 73464 KB Output is correct
21 Correct 34 ms 76748 KB Output is correct