oj.uz

Submission #114818

# Submission time Handle Problem Language Result Execution time Memory
114818 2019-06-03T04:37:52 Z Shafin666 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 696 ms 81272 KB 
#include <iostream>

const int maxn = 1e6+10;
int state[maxn], parent[maxn][25];
int depth[maxn]; char letter[maxn];
int stat = 0, command = 0;

void Init() {}

void TypeLetter(char L) {
    stat++, command++;
    state[command] = stat;
    letter[stat] = L;

    int par = state[command - 1];
    depth[stat] = depth[par] + 1;
    parent[stat][0] = par;
    letter[stat] = L;

    for(int i = 1; i <= 20; i++)
        parent[stat][i] = parent[parent[stat][i-1]][i-1];
}

void UndoCommands(int U) {
    command++;
    state[command] = state[command - U - 1];
}

char GetLetter(int P) {
    int cur = state[command];
    P = depth[cur] - P - 1;

    for(int i = 0; i <= 20; i++)
        if(P & (1 << i))
            cur = parent[cur][i];

    return letter[cur];
}

Subtask #1
5.0 / 5.0

# 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 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 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# 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 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 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 65976 KB Output is correct
2 Correct 644 ms 73544 KB Output is correct
3 Correct 381 ms 72936 KB Output is correct
4 Correct 372 ms 60132 KB Output is correct
5 Correct 497 ms 63972 KB Output is correct
6 Correct 435 ms 79504 KB Output is correct
7 Correct 440 ms 42020 KB Output is correct
8 Correct 407 ms 60296 KB Output is correct
9 Correct 696 ms 81272 KB Output is correct
10 Correct 211 ms 60212 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 57400 KB Output is correct
2 Correct 657 ms 52436 KB Output is correct
3 Correct 362 ms 57304 KB Output is correct
4 Correct 356 ms 45052 KB Output is correct
5 Correct 384 ms 61688 KB Output is correct
6 Correct 418 ms 58204 KB Output is correct
7 Correct 392 ms 61656 KB Output is correct
8 Correct 546 ms 32712 KB Output is correct
9 Correct 688 ms 54264 KB Output is correct
10 Correct 200 ms 59512 KB Output is correct