Submission #103615

#	Time	Username	Problem	Language	Result	Execution time	Memory
103615		alexpetrescu	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	505 ms	63968 KiB

scrivener

#define MAXN 1000009
#define LOGN 20

int t[LOGN + 1][MAXN];
char val[MAXN];
int h[MAXN], stare[MAXN];
int nodes, stari;

void Init() {
    nodes = 1;
    stari = 1;
    stare[stari] = 1;
}

void TypeLetter(char L) {
    nodes++;
    h[nodes] = h[stare[stari]] + 1;
    t[0][nodes] = stare[stari];
    int x = 1;
    while (t[x - 1][nodes]) {
        t[x][nodes] = t[x - 1][t[x - 1][nodes]];
        x++;
    }
    val[nodes] = L;
    stare[++stari] = nodes;
}

void UndoCommands(int U) {
    stare[stari + 1] = stare[stari - U];
    stari++;
}

char GetLetter(int P) {
    int nod = stare[stari];
    int cat = h[nod] - P - 1;
    for (int i = 0; i < LOGN; i++)
        if (cat & (1 << i))
            nod = t[i][nod];
    return val[nod];
}

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