# | 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];
}