Submission #31472

#	Time	Username	Problem	Language	Result	Execution time	Memory
31472		top34051	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	793 ms	100784 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define MLOG 20

int n,sz;
int ver[maxn], len[maxn];
int par[maxn][23];
char val[maxn];

void Init() {
    len[0] = -1;
}

void TypeLetter(char L) {
    sz++;
    ver[sz] = sz;
    len[sz] = len[sz-1] + 1;
    val[sz] = L;
    par[sz][0] = ver[sz-1];
    for(int i=1;i<=MLOG;i++) par[sz][i] = par[par[sz][i-1]][i-1];
}

void UndoCommands(int U) {
    sz++;
    ver[sz] = ver[sz-U-1];
    len[sz] = len[sz-U-1];
}

char GetLetter(int P) {
    int x;
    x = ver[sz];
    P = len[x]-P;
    for(int i=0;i<=MLOG;i++) {
        if(P&1) x = par[x][i];
        P/=2;
    }
    return val[x];
}

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