Submission #79088

#	Time	Username	Problem	Language	Result	Execution time	Memory
79088		TAMREF	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	585 ms	115688 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e6 + 5;
const int lg = 20;
int D[mx], I[mx];
char X[mx];
int p[mx][lg];
int n;

void Init() {
}

void TypeLetter(char L) {
    ++n;
    I[n] = n; X[n] = L;
    p[n][0] = I[n-1];
    D[n] = D[I[n-1]] + 1;
    for(int j = 1; 1 << j <= D[n]; j++){
        p[n][j] = p[p[n][j-1]][j-1];
    }
}

void UndoCommands(int U) {
    ++n;
    I[n] = I[n - 1 - U];
}

char GetLetter(int P) {
    ++P;
    int b = I[n], dlt = D[b] - P;
    for(int j = 0; j < lg; j++){
        if(dlt >> j & 1) b = p[b][j];
    }
    return X[b];
}

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