Submission #850204

#	Time	Username	Problem	Language	Result	Execution time	Memory
850204		abcvuitunggio	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	334 ms	143184 KiB

scrivener

char last,c[1000001];
int p[1000001][20],child[1000001][26],d[1000001],q[1000001],id,cur,idx;
void Init(){}
void TypeLetter(char L){
    if (!child[cur][L-'a']){
        child[cur][L-'a']=++idx;
        c[idx]=L;
        p[idx][0]=cur;
        d[idx]=d[cur]+1;
        for (int i=1;i<20;i++)
            p[idx][i]=p[p[idx][i-1]][i-1];
    }
    cur=child[cur][L-'a'];
    id++;
    q[id]=cur;
}
void UndoCommands(int U){
    cur=q[id-U];
    id++;
    q[id]=cur;
}
char GetLetter(int P){
    int k=d[cur]-P-1,u=cur;
    for (int i=19;i>=0;i--)
        if ((1<<i)<=k){
            u=p[u][i];
            k-=(1<<i);
        }
    return c[u];
}

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