Submission #821741

#	Time	Username	Problem	Language	Result	Execution time	Memory
821741		annabeth9680	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	276 ms	67144 KiB

scrivener

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

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