제출 #140871

#제출 시각아이디문제언어결과실행 시간메모리
140871silxikys크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
100 / 100
799 ms133752 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 1e6+6, maxk = 20; struct Node { Node* par[maxk]; char c; int len; Node(char cc = '#', Node *p = NULL) { c = cc; par[0] = p; len = p == NULL ? 0 : p->len + 1; for (int k = 1; k < maxk; k++) { if (par[k-1] == NULL) break; par[k] = par[k-1]->par[k-1]; } } }; string s(Node *test) { string s; while (test != NULL) { s = s + test->c; test = test->par[0]; } reverse(s.begin(),s.end()); return s; } Node* nodes[maxn]; int q; void Init() { q = 0; nodes[q++] = new Node(); } void TypeLetter(char L) { nodes[q] = new Node(L,nodes[q-1]); q++; //cout << q << ": " << s(nodes[q-1]) << '\n'; } void UndoCommands(int U) { nodes[q] = nodes[q-U-1]; q++; //cout << q << ": " << s(nodes[q-1]) << '\n'; } char GetLetter(int P) { Node *curr = nodes[q-1]; P = curr->len - 1 - P; for (int k = maxk-1; k >= 0; k--) { if (1<<k <= P) { P -= 1<<k; curr = curr->par[k]; } } //cout << s(nodes[q-1]) << '\n'; return curr->c; } /* int main() { Init(); TypeLetter('a'); TypeLetter('b'); cout << GetLetter(1) << '\n'; TypeLetter('d'); UndoCommands(2); UndoCommands(1); cout << GetLetter(2) << '\n'; TypeLetter('e'); UndoCommands(1); UndoCommands(5); TypeLetter('c'); cout << GetLetter(2) << '\n'; UndoCommands(2); cout << GetLetter(2) << '\n'; } */
#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...