Submission #18725

#TimeUsernameProblemLanguageResultExecution timeMemory
18725ggohCrayfish scrivener (IOI12_scrivener)C++98
100 / 100
408 ms87988 KiB
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];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...