# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
120470 | 2019-06-24T15:47:07 Z | KieranHorgan | Crayfish scrivener (IOI12_scrivener) | C++17 | 0 ms | 0 KB |
#include "scrivener.h" #include <bits/stdc++.h> using namespace std; char charOfStep[1000005]; int depth[1000005]; int kthAncestor[1000005][21]; int curStep = 0; void Init() {} void TypeLetter(char L) { curStep++; charOfStep[curStep] = L; depth[curStep] = depth[curStep-1]+1; kthAncestor[curStep][0] = curStep-1; for(int i = 1; 1<<i <= depth[curStep]; i++) kthAncestor[curStep][i] = kthAncestor[kthAncestor[curStep][i-1]][i-1]; } void UndoCommands(int U) { curStep++; charOfStep[curStep] = charOfStep[curStep-1-U]; depth[curStep] = depth[curStep-1-U]; kthAncestor[curStep][0] = kthAncestor[curStep-1-U][0]; for(int i = 1; 1<<i <= depth[curStep]; i++) kthAncestor[curStep][i] = kthAncestor[kthAncestor[curStep][i-1]][i-1]; } char GetLetter(int P) { int node = curStep; for(int i = 21; i >= 0; i--) if(depth[node] - (1<<i) >= P+1) node = kthAncestor[node][i]; return charOfStep[node]; }