Submission #851991

#	Time	Username	Problem	Language	Result	Execution time	Memory
851991		12345678	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	286 ms	70272 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5, mx=20;
int p[nx][mx], t, c[nx], cur, sz[nx];
vector<int> v;

void Init() {
}

void TypeLetter(char L) {
    t++; p[t][0]=cur; sz[t]=sz[cur]+1;
    for (int i=1; i<mx; i++) p[t][i]=p[p[t][i-1]][i-1];
    cur=t; c[cur]=L; v.push_back(cur);
}

void UndoCommands(int U) {
    cur=v[max((int) v.size()-U-1, 0)];
    v.push_back(cur);
}

char GetLetter(int P) {
    int k=sz[cur]-P-1, tmp=cur;
    for (int i=0; i<mx; i++) if (k&(1<<i)) tmp=p[tmp][i];
    return c[tmp];
}

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