Submission #931997

#TimeUsernameProblemLanguageResultExecution timeMemory
931997AlphaMale06Crayfish scrivener (IOI12_scrivener)C++17
100 / 100
506 ms98776 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back struct node{ char c; int p[20]; int h; }; vector<node> trie; node make(int par, char ch){ node ret; ret.c=ch; ret.h=trie[par].h+1; ret.p[0]=par; for(int i=1; i<20; i++){ ret.p[i]=trie[ret.p[i-1]].p[i-1]; } return ret; } int cur=0; const int N = 1000010; int curs[N]; int cnt; void Add(char c){ curs[cnt]=trie.size(); trie.pb(make(cur, c)); cur=curs[cnt]; cnt++; } char lift(int v, int to){ int ret=v; for(int i=19; i>=0; i--){ if(trie[trie[ret].p[i]].h >= to){ ret=trie[ret].p[i]; } } return trie[ret].c; } void TypeLetter(char c) { Add(c); } void UndoCommands(int num) { curs[cnt]=curs[cnt-1-num]; cur=curs[cnt]; cnt++; } char GetLetter(int ind) { return lift(cur, ind+1); } void Init() { node first; first.h=0; for(int i=0; i<20; i++)first.p[i]=0; first.c=0; trie.pb(first); curs[0]=0; cnt=1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...