제출 #577655

#제출 시각아이디문제언어결과실행 시간메모리
577655AngusWong크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++17
100 / 100
592 ms162452 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int N=1e6+1; int cur, up[N][21]; vector<char> trie; vector<vector<int> > nxt; vector<int> len, step; void Init() { cur=0; trie.clear(); nxt.clear(); len.clear(); trie.push_back('!'); nxt.push_back(vector<int>(26, -1)); len.push_back(0); for (int i=0; i<=20; i++) up[0][i]=-1; step.clear(); step.push_back(cur); } void TypeLetter(char L) { if (nxt[cur][L-'a']==-1){ trie.push_back(L); nxt.push_back(vector<int>(26, -1)); nxt[cur][L-'a']=trie.size()-1; len.push_back(len[cur]+1); up[trie.size()-1][0]=cur; for (int i=1; i<=20; i++){ up[trie.size()-1][i]=(up[trie.size()-1][i-1]==-1? -1: up[up[trie.size()-1][i-1]][i-1]); } } cur=nxt[cur][L-'a']; step.push_back(cur); } void UndoCommands(int U) { cur=step[step.size()-U-1]; step.push_back(cur); } char GetLetter(int P) { P=len[cur]-P-1; int t=cur; for (int i=20; i>=0; i--){ if (P>=(1<<i)){ P-=(1<<i); t=up[t][i]; } } return trie[t]; }
#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...