# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
104241 | 2019-04-04T11:28:57 Z | arman_ferdous | Crayfish scrivener (IOI12_scrivener) | C++14 | 1000 ms | 190484 KB |
// #include "grader.h" #include <bits/stdc++.h> using namespace std; struct node{ char c; int d; node *to[26]; vector<node*> p; node() { d = -1; for(int i = 0; i < 26; i++) to[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.push_back(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]) { if((trie_pos->p[j-1])->p.size() > j-1) trie_pos->p.push_back((trie_pos->p[j-1])->p[j-1]); else break; } else break; } } 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 384 KB | Output is correct |
6 | Correct | 3 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 | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 3 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 | 1 ms | 324 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 896 KB | Output is correct |
2 | Correct | 6 ms | 896 KB | Output is correct |
3 | Correct | 5 ms | 896 KB | Output is correct |
4 | Correct | 5 ms | 1280 KB | Output is correct |
5 | Correct | 4 ms | 896 KB | Output is correct |
6 | Correct | 6 ms | 1792 KB | Output is correct |
7 | Correct | 7 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 1408 KB | Output is correct |
9 | Correct | 7 ms | 1536 KB | Output is correct |
10 | Correct | 5 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1079 ms | 190484 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1092 ms | 145412 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |