Submission #1164449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164449		AlgorithmWarrior	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	263 ms	68368 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e6+5;
int const LOG=22;
vector<int>stare;
int h[MAX];
int lift[MAX][LOG];
int id;
char carac[MAX];

void Init(){
    stare.push_back(0);
    h[0]=-1;
}

void TypeLetter(char L){
    int tata=stare.back();
    ++id;
    stare.push_back(id);
    carac[id]=L;
    h[id]=h[tata]+1;
    lift[id][0]=tata;
    int i;
    for(i=1;i<LOG;++i)
        lift[id][i]=lift[lift[id][i-1]][i-1];
}

void UndoCommands(int U){
    stare.push_back(stare[stare.size()-U-1]);
}

char GetLetter(int P){
    int nod=stare.back();
    int dif=h[nod]-P;
    int i;
    for(i=0;i<LOG;++i)
        if(dif&(1<<i))
            nod=lift[nod][i];
    return carac[nod];
}

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