oj.uz

Submission #17133

# Submission time Handle Problem Language Result Execution time Memory
17133 2015-11-06T09:30:37 Z murat Crayfish scrivener (IOI12_scrivener) C++
100 / 100
 454 ms 183356 KB 
#include<bits/stdc++.h>

using namespace std;

const int logN = 20;
const int N = 2e6 + 5;

static int depth[N], node, lca[N][logN+1], C, S, W[N];
char col[N];

void Init() {
}

void TypeLetter(char L) {
    W[++S] = ++C;
    col[C] = L;
    lca[C][0] = node;
    node = C;
    for(int i = 1; i <= logN; i++)
        lca[node][i] = lca[lca[node][i-1]][i-1];
    depth[node] = depth[lca[node][0]] + 1;
}

void UndoCommands(int U) {
    node = W[S - U];
    W[++S] = node;
}

char GetLetter(int P) {
    P = depth[node] - P - 1;
    int tt = node;
    for(int i = logN; i >= 0; i--)
        if((1 << i) <= P) {
            P -= (1 << i);
            tt = lca[tt][i];
        }
    return col[tt];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 183356 KB Output is correct
2 Correct 0 ms 183356 KB Output is correct
3 Correct 0 ms 183356 KB Output is correct
4 Correct 0 ms 183356 KB Output is correct
5 Correct 0 ms 183356 KB Output is correct
6 Correct 0 ms 183356 KB Output is correct
7 Correct 0 ms 183356 KB Output is correct
8 Correct 0 ms 183356 KB Output is correct
9 Correct 0 ms 183356 KB Output is correct
10 Correct 0 ms 183356 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 183356 KB Output is correct
2 Correct 0 ms 183356 KB Output is correct
3 Correct 0 ms 183356 KB Output is correct
4 Correct 0 ms 183356 KB Output is correct
5 Correct 0 ms 183356 KB Output is correct
6 Correct 0 ms 183356 KB Output is correct
7 Correct 0 ms 183356 KB Output is correct
8 Correct 0 ms 183356 KB Output is correct
9 Correct 0 ms 183356 KB Output is correct
10 Correct 0 ms 183356 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 183356 KB Output is correct
2 Correct 0 ms 183356 KB Output is correct
3 Correct 0 ms 183356 KB Output is correct
4 Correct 0 ms 183356 KB Output is correct
5 Correct 2 ms 183356 KB Output is correct
6 Correct 2 ms 183356 KB Output is correct
7 Correct 0 ms 183356 KB Output is correct
8 Correct 2 ms 183356 KB Output is correct
9 Correct 0 ms 183356 KB Output is correct
10 Correct 0 ms 183356 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 183356 KB Output is correct
2 Correct 368 ms 183356 KB Output is correct
3 Correct 328 ms 183356 KB Output is correct
4 Correct 316 ms 183356 KB Output is correct
5 Correct 348 ms 183356 KB Output is correct
6 Correct 288 ms 183356 KB Output is correct
7 Correct 315 ms 183356 KB Output is correct
8 Correct 283 ms 183356 KB Output is correct
9 Correct 431 ms 183356 KB Output is correct
10 Correct 210 ms 183356 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 183356 KB Output is correct
2 Correct 439 ms 183356 KB Output is correct
3 Correct 303 ms 183356 KB Output is correct
4 Correct 329 ms 183356 KB Output is correct
5 Correct 307 ms 183356 KB Output is correct
6 Correct 322 ms 183356 KB Output is correct
7 Correct 334 ms 183356 KB Output is correct
8 Correct 374 ms 183356 KB Output is correct
9 Correct 454 ms 183356 KB Output is correct
10 Correct 216 ms 183356 KB Output is correct