Submission #447879

#	Time	Username	Problem	Language	Result	Execution time	Memory
447879		FEDIKUS	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	634 ms	136892 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;
const int logg=22;
int trie[maxn][26];
int lift[maxn][logg];
char slovo[maxn];
bool uradio[maxn];

int gde[maxn];
int trengde=0;
int koliko=1;

void probaj(int poz,int prosli){
    if(uradio[poz]) return;
    lift[poz][0]=prosli;
    for(int i=1;i<logg;i++){
        lift[poz][i]=lift[lift[poz][i-1]][i-1];
    }
    uradio[poz]=true;
}

int dalje(int poz,int a){
    if(trie[poz][a]==0) trie[poz][a]=koliko++;
    probaj(trie[poz][a],poz);
    return trie[poz][a];
}

int koji(){
    int pom=gde[trengde];
    int ret=0;
    for(int i=logg-1;i>=0;i--){
        if(lift[pom][i]==0) continue;
        pom=lift[pom][i];
        ret+=(1<<i);
    }
    return ret;
}

int skoci(int x){
    int wtf=gde[trengde];
    for(int i=logg-1;i>=0;i--){
        if((1<<i)>x) continue;
        x-=(1<<i);
        wtf=lift[wtf][i];
    }
    return wtf;
}

void Init(){
    probaj(0,0);
}

void TypeLetter(char L) {
    gde[trengde+1]=dalje(gde[trengde],L-'a');
    trengde++;
    slovo[gde[trengde]]=L;
}

void UndoCommands(int U) {
    gde[trengde+1]=gde[trengde-U];
    trengde++;
}

char GetLetter(int P) {
    return slovo[skoci(koji()-P)];
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40