/*
Solution for Scrivener, with TypeLetter and GetLetter in O(log N) and UndoCommands in O(1).
Author: Matteo Boscariol
*/
#include<cstdlib>
#define MAXC 1000000
#define LOGMAXC 20
class node {
public:
char l;
node** parents;
int depth;
node(char letter, node* parent) {
l = letter;
if(parent == NULL) {
depth=-1;
parents = new node*[1];
parents[0] = NULL;
}
else {
depth=parent->depth+1;
parents = new node*[LOGMAXC];
parents[0] = parent;
for(int i=1, j=2; j<=depth+1; i++, j*=2) {
parents[i] = parents[i-1]->parents[i-1];
}
}
};
};
node** command_base;
int n_commands;
node* current_position;
node* tree_root;
void Init() {
command_base = new node*[MAXC];
n_commands = 0;
current_position = tree_root = new node('\0',NULL);
}
void TypeLetter(char L) {
command_base[n_commands] = current_position;
n_commands++;
node* n = new node(L, current_position);
current_position = n;
}
void UndoCommands(int U) {
node *n = command_base[n_commands - U];
command_base[n_commands] = current_position;
n_commands++;
current_position = n;
}
char GetLetter(int P) {
node* n = current_position;
int distance = current_position->depth - P;
for(int shift = LOGMAXC; shift >= 0; shift--) {
if((distance >> shift)%2 == 1)
n = n->parents[shift];
}
return n->l;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
8732 KB |
Output is correct |
2 |
Correct |
0 ms |
8732 KB |
Output is correct |
3 |
Correct |
0 ms |
8732 KB |
Output is correct |
4 |
Correct |
0 ms |
8732 KB |
Output is correct |
5 |
Correct |
0 ms |
8732 KB |
Output is correct |
6 |
Correct |
0 ms |
8732 KB |
Output is correct |
7 |
Correct |
0 ms |
8732 KB |
Output is correct |
8 |
Correct |
0 ms |
8732 KB |
Output is correct |
9 |
Correct |
0 ms |
8732 KB |
Output is correct |
10 |
Correct |
0 ms |
8732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
8732 KB |
Output is correct |
2 |
Correct |
0 ms |
8732 KB |
Output is correct |
3 |
Correct |
0 ms |
8732 KB |
Output is correct |
4 |
Correct |
0 ms |
8732 KB |
Output is correct |
5 |
Correct |
0 ms |
8732 KB |
Output is correct |
6 |
Correct |
0 ms |
8732 KB |
Output is correct |
7 |
Correct |
0 ms |
8732 KB |
Output is correct |
8 |
Correct |
0 ms |
8732 KB |
Output is correct |
9 |
Correct |
0 ms |
8732 KB |
Output is correct |
10 |
Correct |
0 ms |
8732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
8996 KB |
Output is correct |
2 |
Correct |
1 ms |
8996 KB |
Output is correct |
3 |
Correct |
0 ms |
8996 KB |
Output is correct |
4 |
Correct |
1 ms |
9260 KB |
Output is correct |
5 |
Correct |
1 ms |
8996 KB |
Output is correct |
6 |
Correct |
1 ms |
9392 KB |
Output is correct |
7 |
Correct |
1 ms |
9392 KB |
Output is correct |
8 |
Correct |
0 ms |
9128 KB |
Output is correct |
9 |
Correct |
0 ms |
9260 KB |
Output is correct |
10 |
Correct |
0 ms |
8996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
684 ms |
126080 KB |
Output is correct |
2 |
Correct |
691 ms |
137960 KB |
Output is correct |
3 |
Correct |
488 ms |
135188 KB |
Output is correct |
4 |
Correct |
448 ms |
106940 KB |
Output is correct |
5 |
Correct |
562 ms |
117632 KB |
Output is correct |
6 |
Correct |
667 ms |
148916 KB |
Output is correct |
7 |
Correct |
581 ms |
72092 KB |
Output is correct |
8 |
Correct |
477 ms |
109316 KB |
Output is correct |
9 |
Correct |
781 ms |
152084 KB |
Output is correct |
10 |
Correct |
310 ms |
110900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
938 ms |
107732 KB |
Output is correct |
2 |
Correct |
851 ms |
95060 KB |
Output is correct |
3 |
Correct |
456 ms |
104036 KB |
Output is correct |
4 |
Correct |
542 ms |
77372 KB |
Output is correct |
5 |
Correct |
523 ms |
113276 KB |
Output is correct |
6 |
Correct |
628 ms |
106412 KB |
Output is correct |
7 |
Correct |
543 ms |
113540 KB |
Output is correct |
8 |
Correct |
669 ms |
54008 KB |
Output is correct |
9 |
Correct |
907 ms |
97172 KB |
Output is correct |
10 |
Correct |
283 ms |
109844 KB |
Output is correct |