| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 970978 | asdasdqwer | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
 
#include "scrivener.h"
 
vector<vector<int>> child;
int actNode;
int actSize;
int lft[1'000'000][21];
char last[1'000'000];
int cnt[1'000'000];
 
void calcJmp(int node) {
    for (int j=1;j<21;j++) {
        lft[node][j] = lft[node][j-1];
        if (lft[node][j] != -1) {
            lft[node][j] = lft[lft[node][j]][j-1];
        }
 
        if (lft[node][j] == -1) {
            break;
        }
    }
}
 
void Init() {
    actNode = 0;
    actSize = 0;
    child.push_back({});
    for (int i=0;i<21;i++) {
        lft[0][i] = -1;
    }
}
 
void append() {
    // append as child of actNode
    actSize++;
    child[actNode].push_back(actSize);
    child.push_back({});
    lft[actSize][0] = actNode;
    last[actSize] = last[actNode];
    cnt[actSize] = cnt[actNode];
    calcJmp(actSize);
    actNode = actSize;
}
 
void TypeLetter(char L) {
    append();
    last[actNode] = L;
    cnt[actNode]++;
}
 
void UndoCommands(int U) {
    actNode = actSize - U;
    append();
}
 
char GetLetter(int P) {
    int pt = actNode;
    for (int i=20;i>=0;i--) {
        if (lft[pt][i] != -1 && cnt[lft[pt][i]] > P) {
            pt = lft[pt][i];
        }
    }
  
    return last[pt];
}
