Submission #955023

#	Time	Username	Problem	Language	Result	Execution time	Memory
955023		parlimoos	Match (CEOI16_match)	C++14	0 / 100	32 ms	63824 KiB

match

//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++;
    }
    // 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){
    cout << l << " " << r << "::\n" << flush;
    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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63