Submission #1191986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191986		LolkasMeep	Crayfish scrivener (IOI12_scrivener)	C++20	74 / 100	578 ms	278092 KiB

scrivener

#include "bits/stdc++.h"
using namespace std;

const int LOG2 = 20;

struct Try{
    Try* parent = NULL;
    Try *children[26] = {NULL};
    int h;
    char chr;

    Try *jump[LOG2] = {NULL};

    Try(char c, Try* p){
        parent = p;
        chr = c;
        if(p==NULL) h = 0;
        else h = parent->h+1;

        Try *now = this;
        for(int i = 0; i < LOG2; i++){
            if(i == 0) now = parent;
            else if(now == NULL) now = NULL;
            else now = now->jump[i-1];
            jump[i] = now;
        }
    }

    Try* add(char c){
        if(children[c-'a'] != NULL) return children[c-'a'];

        children[c-'a'] = new Try(c, this);

        return children[c-'a'];
    }

    char get(int j){
        Try *now = this;

        for(int i = LOG2; i >= 0; i--){
            // cout << j << '\n';
            if(1<<i > j) continue;
            j -= 1<<i;
            now = now->jump[i];
        }

        return now->chr;
    }
};

int i=1;
Try *tries[1000005];
void Init(){
    tries[0] = NULL;
};
void TypeLetter(char L){
    tries[i]=new Try(L, tries[i-1]);
    i++;
}
void UndoCommands(int U){
    tries[i]=tries[i-U-1];
    i++;
}
char GetLetter(int P){
    return tries[i-1]->get(tries[i-1]->h-P);
}

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