Submission #65758

#	Time	Username	Problem	Language	Result	Execution time	Memory
65758		aquablitz11	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	967 ms	63508 KiB

scrivener

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

using pic = pair<int, char>;
const int N = 1<<20;
const int LN = 20;
int cnt;
char chr[N];
int len[N];
int par[N][LN];
int ptr[N];

inline int link(int p, char c)
{
    chr[++cnt] = c;
    par[cnt][0] = p;
    len[cnt] = len[p]+1;
    for (int i = 1; i < LN; ++i)
        par[cnt][i] = par[par[cnt][i-1]][i-1];
    return cnt;
}

void Init() {
    //printf("Init()\n");
}

int vc;
void TypeLetter(char L) {
    //printf("TypeLetter(%c)\n", L);
    ++vc;
    ptr[vc] = link(ptr[vc-1], L);
}

void UndoCommands(int U)
{
    //printf("UndoCommands(%d)\n", U);
    U = min(U, vc);
    ++vc;
    ptr[vc] = ptr[vc-U-1];
}

char GetLetter(int P)
{
    int u = ptr[vc];
    P = len[ptr[vc]]-P-1;
    for (int i = LN-1; i >= 0; --i)
        if ((1<<i)&P) u = par[u][i];
    //printf("GetLetter(%d) = %c\n", P, ans);
    return chr[u];
}

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