# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237457 | 2020-06-06T16:57:13 Z | nicolaalexandra | Crayfish scrivener (IOI12_scrivener) | C++14 | 645 ms | 97400 KB |
#include <bits/stdc++.h> #define DIM 1000010 using namespace std; int v[DIM],tip[DIM],fth[DIM],level[DIM],dp[DIM][20]; int nr_nodes,k; void Init(){} void TypeLetter (char L) { int nod = v[k]; int vecin = ++nr_nodes; v[++k] = nr_nodes; //L[nod].push_back(vecin); //L[vecin].push_back(nod); tip[vecin] = L - 'a'; /// fth[i] - primul nod (in sus) care e litera if (tip[nod] == -1) /// e nod de undo fth[vecin] = fth[nod]; else fth[vecin] = nod; level[vecin] = 1 + level[fth[vecin]]; /// stramosi 2^k dp[vecin][0] = fth[vecin]; for (int i=1;i<=20;i++) dp[vecin][i] = dp[dp[vecin][i-1]][i-1]; } void UndoCommands(int U) { int nod = v[k-U]; int vecin = ++nr_nodes; v[++k] = nr_nodes; tip[vecin] = -1; if (tip[nod] == -1) fth[vecin] = fth[nod]; else fth[vecin] = nod; } char GetLetter(int P) { int nod = v[k]; if (tip[nod] == -1) nod = fth[nod]; int val = level[nod] - P - 1; for (int i=20;i>=0;i--){ if ((1<<i) <= val){ val -= (1<<i); nod = dp[nod][i]; } } return (char)(tip[nod] + 'a'); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 4 ms | 384 KB | Output is correct |
9 | Correct | 5 ms | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 5 ms | 376 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 512 KB | Output is correct |
2 | Correct | 6 ms | 672 KB | Output is correct |
3 | Correct | 8 ms | 768 KB | Output is correct |
4 | Correct | 6 ms | 768 KB | Output is correct |
5 | Correct | 6 ms | 768 KB | Output is correct |
6 | Correct | 5 ms | 1024 KB | Output is correct |
7 | Correct | 6 ms | 768 KB | Output is correct |
8 | Correct | 6 ms | 896 KB | Output is correct |
9 | Correct | 6 ms | 768 KB | Output is correct |
10 | Correct | 7 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 67576 KB | Output is correct |
2 | Correct | 446 ms | 86520 KB | Output is correct |
3 | Correct | 418 ms | 86648 KB | Output is correct |
4 | Correct | 477 ms | 92024 KB | Output is correct |
5 | Correct | 429 ms | 80504 KB | Output is correct |
6 | Correct | 370 ms | 93660 KB | Output is correct |
7 | Correct | 515 ms | 82296 KB | Output is correct |
8 | Correct | 443 ms | 91528 KB | Output is correct |
9 | Correct | 474 ms | 87416 KB | Output is correct |
10 | Correct | 293 ms | 97400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 517 ms | 62200 KB | Output is correct |
2 | Correct | 570 ms | 58872 KB | Output is correct |
3 | Correct | 426 ms | 73464 KB | Output is correct |
4 | Correct | 456 ms | 65656 KB | Output is correct |
5 | Correct | 391 ms | 83960 KB | Output is correct |
6 | Correct | 463 ms | 86648 KB | Output is correct |
7 | Correct | 425 ms | 86520 KB | Output is correct |
8 | Correct | 645 ms | 74820 KB | Output is correct |
9 | Correct | 638 ms | 71672 KB | Output is correct |
10 | Correct | 288 ms | 96112 KB | Output is correct |