Submission #310883

#	Time	Username	Problem	Language	Result	Execution time	Memory
310883		amunduzbaev	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	562 ms	90588 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
const int N=1e6+5;
int curnode, node, len, par[N][30], pos[N], depth[N];
char value[N];

void Init() {}

void TypeLetter(char l) {
    len++;
    node++;
    depth[node]=depth[curnode]+1;
    value[node]=l;
    par[node][0]=curnode;
    pos[len]=node;
    curnode=node;
    for(int i=1;i<23;i++){
        par[node][i]=par[par[node][i-1]][i-1];
    }
}

void UndoCommands(int u) {
    curnode=pos[len-u];
    len++;
    pos[len]=curnode;

}
char GetLetter(int p) {
    int ans=curnode;
    int go=depth[ans]-p-1;
    for(int i=0;i<23;i++){
        if((go>>i)%2==1)
            ans=par[ans][i];
    }
    return value[ans];
}
/*

14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2

*/

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