제출 #255416

#제출 시각아이디문제언어결과실행 시간메모리
255416ChrisT크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++17
100 / 100
704 ms165472 KiB
#include <bits/stdc++.h> using namespace std; const int LOG = 20; vector<int> ans; int trie[1000001][26], depth[1000001], p[1000001][21], inc; char letter[1000001]; void Init(){ inc = 0; memset(p,-1,sizeof p); ans.push_back(0); } void TypeLetter(char L){ int cur = ans[ans.size()-1], ch = L-'a'; if (!trie[cur][ch]) { trie[cur][ch] = ++inc; depth[inc] = depth[cur] + 1; p[inc][0] = cur; for (int x = 1; x <= LOG; x++) if (~p[inc][x-1]) p[inc][x] = p[p[inc][x-1]][x-1]; letter[inc] = L; } ans.push_back(trie[cur][ch]); } void UndoCommands(int U){ ans.push_back(ans[ans.size()-1-U]); } char GetLetter(int P){ int cur = ans.back(); P++; for (int x = LOG; x >= 0; x--) if (~p[cur][x] && depth[p[cur][x]] >= P) cur = p[cur][x]; return letter[cur]; }
#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...