// #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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
356 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
896 KB |
Output is correct |
2 |
Correct |
5 ms |
896 KB |
Output is correct |
3 |
Correct |
4 ms |
896 KB |
Output is correct |
4 |
Correct |
4 ms |
1536 KB |
Output is correct |
5 |
Correct |
3 ms |
940 KB |
Output is correct |
6 |
Correct |
4 ms |
1792 KB |
Output is correct |
7 |
Correct |
5 ms |
1792 KB |
Output is correct |
8 |
Correct |
4 ms |
1280 KB |
Output is correct |
9 |
Correct |
5 ms |
1408 KB |
Output is correct |
10 |
Correct |
4 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1032 ms |
225628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1075 ms |
171756 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |