Submission #820151

#	Time	Username	Problem	Language	Result	Execution time	Memory
820151		BT21tata	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	376 ms	90492 KiB

scrivener

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

int que, up[1000006][21], len[1000006];
char c[1000006];

void Init() {}

void TypeLetter(char L)
{
    que++;
    c[que]=L;
    up[que][0]=que-1;
    len[que]=len[que-1]+1;
    for(int i=1; i<21; i++)
        up[que][i]=up[up[que][i-1]][i-1];
}

void UndoCommands(int U)
{
    que++;
    len[que]=len[que-1-U];
    c[que]=c[que-1-U];
    for(int i=0; i<21; i++)
        up[que][i]=up[que-1-U][i];
}

char GetLetter(int p)
{
    p=len[que]-1-p;
    int cur=que;
    for(int i=20; i>=0; i--)
    {
        if(p-(1<<i)>=0)
        {
            p-=(1<<i);
            cur=up[cur][i];
        }
    }
    return c[cur];
}

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