# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1617 | 2013-07-10T15:11:39 Z | tncks0121 | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++ | 0 ms | 0 KB |
const int MAXC = 1000005; const int lgMAXC = 20; struct node{ char letter; int level; node* parent[lgMAXC]; node(char letter, node* par): letter(letter){ parent[0] = par; if(par != NULL) level = par->level + 1; else level = 0; for(int i=1; i<lgMAXC; i++){ if(parent[i-1] == NULL) parent[i] = NULL; else parent[i] = parent[i-1]->parent[i-1]; } } }; node* Commands[MAXC]; node* now; int N; void Init(){ now = new node(0, NULL); Commands[1] = now; N = 1; } void TypeLetter(char L){ Commands[++N] = new node(L, now); now = Commands[N]; } void UndoCommands(unsigned int U){ int val = N - U; Commands[++N] = Commands[val]; now = Commands[N]; } char GetLetter(unsigned int P){ node* tmp = now; int L = now->level - P; for(int i=0; (1<<i)<=L; i++) if(L & (1<<i)){ tmp = tmp->parent[i]; } return tmp->letter; }