| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 104239 | 2019-04-04T11:06:48 Z | arman_ferdous | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KB |
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
char c; int d;
node *to[26];
node *p[20];
node() {
d = -1;
for(int i = 0; i < 26; i++) to[i] = NULL;
for(int i = 0; i < 20; i++) p[i] = NULL;
}
};
using pnode = node*;
pnode root, trie_pos;
pnode state[1000010]; int ptr;
void Init() {
root = new node();
ptr = 0; state[0] = root;
trie_pos = root;
}
void TypeLetter(char L) {
int id = L - 'a';
if(!trie_pos->to[id])
trie_pos->to[id] = new node();
trie_pos->to[id]->d = trie_pos->d + 1; // update depth
trie_pos->to[id]->p[0] = trie_pos; // set new childs parent
trie_pos = trie_pos->to[id]; // move it to child
state[++ptr] = trie_pos; // update state vector
trie_pos->c = L; // update containing char
for(int j = 1; j < 20; j++)
if(trie_pos->p[j-1])
trie_pos->p[j] = (trie_pos->p[j-1])->p[j-1];
}
void UndoCommands(int U) {
state[ptr+1] = state[max(0,ptr-U)]; ptr++;
trie_pos = state[ptr];
}
char GetLetter(int P) {
pnode cur = trie_pos;
int need = trie_pos->d - P;
for(int j = 19; j >= 0; j--)
if(need >= (1<<j)) {
need -= (1<<j);
cur = cur->p[j];
}
return cur->c;
}