Submission #815711

#	Time	Username	Problem	Language	Result	Execution time	Memory
815711		annabeth9680	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	307 ms	67212 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+25;
int curop,sz;
char arr[MAXN];
int ops[MAXN],par[MAXN][20],dep[MAXN];
void Init(){
    curop = 1;
    sz = 1;
    ops[curop] = 1;
    dep[sz] = 0;
    for(int i = 1;i<20;++i){
        par[1][i] = 1;
    }
}
void TypeLetter(char L){
    curop++; sz++;
    ops[curop] = sz;
    arr[sz] = L;
    dep[sz] = dep[ops[curop-1]]+1;
    par[sz][0] = ops[curop-1];
    for(int i = 1;i<20;++i){
        par[sz][i] = par[par[sz][i-1]][i-1];
    }
}
void UndoCommands(int U){
    curop++;
    ops[curop] = ops[curop-U-1];
}
char GetLetter(int P){
    P++; int cur = ops[curop];
    int d = dep[cur]-P;
    for(int i = 0;i<20;++i){
        if((d >> i)&1){
            cur = par[cur][i];
        }
    }
    return arr[cur];
}

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