Submission #596225

#	Time	Username	Problem	Language	Result	Execution time	Memory
596225		Bench0310	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	621 ms	67204 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1000000;
int nodes=0;
char c[N+1];
int depth[N];
int p[N+1][20];
int cnt=0;
int pos[N+1];

void Init(){}

void TypeLetter(char L)
{
    cnt++;
    int a=pos[cnt-1];
    int to=++nodes;
    depth[to]=depth[a]+1;
    p[to][0]=a;
    for(int i=1;i<20;i++) p[to][i]=p[p[to][i-1]][i-1];
    pos[cnt]=to;
    c[to]=L;
}

void UndoCommands(int U)
{
    cnt++;
    pos[cnt]=pos[cnt-U-1];
}

char GetLetter(int P)
{
    P++;
    int a=pos[cnt];
    for(int i=19;i>=0;i--) if(depth[p[a][i]]>=P) a=p[a][i];
    return c[a];
}

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