# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62921 | 2018-07-30T20:36:27 Z | theknife2001 | Crayfish scrivener (IOI12_scrivener) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; const int N=1e6+55; int trie[N*2][26]; char letter[N]; int p[N][22]; int a[N]; int l[N]; int node; int cnt=1; int k=0; void Init() { node=cnt++; memset(trie,-1,sizeof trie); } int c,temp,nd; void TypeLetter(char L) { c=L-'a'; temp=node; if(trie[node][c]==-1) trie[node][c]=cnt++; node=trie[node][c]; letter[node]=L; a[k]=node; if(k!=0) l[k]=l[k-1]+1; else l[k]=1; if(p[node][0]==0) { p[node][0]=temp; // for(int i=1;i<21;i++) // { // p[node][i]=p[p[node][i-1]][i-1]; // if(p[node][i]==0) // break; // } } k++; } void UndoCommands(int U) { node=a[k-U-1]; l[k]=l[k-U-1]; a[k]=node; k++; } char GetLetter(int P) { P=l[k-1]-P-1; nd=node; while(P--) nd=p[nd][0] //for(int i=20;i>=0;i--) //{ //if((P&(1<<i))) // nd=p[nd][i]; //} return letter[nd]; }