Submission #18725

#	Time	Username	Problem	Language	Result	Execution time	Memory
18725		ggoh	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	408 ms	87988 KiB

scrivener

int go[1000005],len[1000005],t=1,par[1000005][20];
char al[1000005];
void Init(){}
void TypeLetter(char L)
{
    al[t]=L;
    len[t]=len[go[t-1]]+1;
    par[t][0]=go[t-1];
    int u=1;
    while(1)
    {
        if(len[t]>=(1<<u)){
        par[t][u]=par[par[t][u-1]][u-1];
        u++;
        }
        else break;
    }
    go[t]=t;
    t++;
}
void UndoCommands(int U)
{
    go[t]=go[t-U-1];
    t++;
}
char GetLetter(int P)
{
    int o=len[go[t-1]];
    o=o-P-1;
    if(o==0)return al[go[t-1]];
    int u=0,h=go[t-1];
    while(o)
    {
        if(o%2)
        {
            h=par[h][u];
        }
        o/=2;
        u++;
    }
    return al[h];
}

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