oj.uz

Submission #103615

# Submission time Handle Problem Language Result Execution time Memory
103615 2019-04-01T08:43:59 Z alexpetrescu Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 505 ms 63968 KB 
#define MAXN 1000009
#define LOGN 20

int t[LOGN + 1][MAXN];
char val[MAXN];
int h[MAXN], stare[MAXN];
int nodes, stari;

void Init() {
    nodes = 1;
    stari = 1;
    stare[stari] = 1;
}

void TypeLetter(char L) {
    nodes++;
    h[nodes] = h[stare[stari]] + 1;
    t[0][nodes] = stare[stari];
    int x = 1;
    while (t[x - 1][nodes]) {
        t[x][nodes] = t[x - 1][t[x - 1][nodes]];
        x++;
    }
    val[nodes] = L;
    stare[++stari] = nodes;
}

void UndoCommands(int U) {
    stare[stari + 1] = stare[stari - U];
    stari++;
}

char GetLetter(int P) {
    int nod = stare[stari];
    int cat = h[nod] - P - 1;
    for (int i = 0; i < LOGN; i++)
        if (cat & (1 << i))
            nod = t[i][nod];
    return val[nod];
}

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 1 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 484 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 4 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 322 ms 51344 KB Output is correct
2 Correct 367 ms 57564 KB Output is correct
3 Correct 318 ms 53112 KB Output is correct
4 Correct 347 ms 44792 KB Output is correct
5 Correct 336 ms 48632 KB Output is correct
6 Correct 262 ms 62712 KB Output is correct
7 Correct 323 ms 33912 KB Output is correct
8 Correct 289 ms 48680 KB Output is correct
9 Correct 376 ms 63968 KB Output is correct
10 Correct 180 ms 42232 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 44920 KB Output is correct
2 Correct 443 ms 40652 KB Output is correct
3 Correct 355 ms 42380 KB Output is correct
4 Correct 442 ms 34296 KB Output is correct
5 Correct 251 ms 48632 KB Output is correct
6 Correct 275 ms 44356 KB Output is correct
7 Correct 259 ms 48404 KB Output is correct
8 Correct 505 ms 26744 KB Output is correct
9 Correct 427 ms 43868 KB Output is correct
10 Correct 178 ms 41976 KB Output is correct