scrivener.cpp

#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

struct state
{
    int depth;
    int parent;
    int parentHop;
    int smallHop;
    char c;
};
#define HOP 5000
#define SMALL_HOP 500

vector<state> states;
vector<int> history;

int findDepth(int node, int target_depth)
{
    while(states[states[node].parentHop].depth > target_depth) node = states[node].parentHop;
    while(states[states[node].smallHop].depth > target_depth) node = states[node].smallHop;
    while(states[node].depth > target_depth) node = states[node].parent;
    return node;
}

state t;
void Init() {
    t.depth = -1;
    t.parent = 0;
    t.parentHop = 0;
    t.smallHop = 0;
    t.c = -1;
    history.push_back(states.size());
    states.push_back(t);
}

void TypeLetter(char L) {
    t.depth = states[history.back()].depth + 1;
    t.c = L;
    t.parent = history.back();
    if(t.depth % HOP == 0)
    {
        t.parentHop = t.parent;
    }
    else
    {
        t.parentHop = states[t.parent].parentHop;
    }

    if(t.depth % SMALL_HOP == 0)
    {
        t.smallHop = t.parent;
    }
    else
    {
        t.smallHop = states[t.parent].smallHop;
    }

    history.push_back(states.size());
    states.push_back(t);
}

void UndoCommands(int U) {
    history.push_back(history[history.size() - U - 1]);
}

char GetLetter(int P) {
    int s = findDepth(history.back(), P);
    return states[s].c;
}