oj.uz

Submission #100311

# Submission time Handle Problem Language Result Execution time Memory
100311 2019-03-10T11:07:50 Z naoai Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 953 ms 146168 KB 
#include <bits/stdc++.h>

using namespace std;

const int sigma = 26;
const int nmax = 1e6 + 5;
const int logmax = 21;

int n, ind;
int p[nmax + 1];

int h[nmax + 1];
int fiu[nmax + 1][sigma + 1];
int d[nmax + 1][logmax + 1];

char ch[nmax + 1];

void Init() {
    n = 1;
    for (int i = 0; i < sigma; ++ i)
        fiu[1][i] = -1;

    ind = 0;
    p[0] = 1;
}

void TypeLetter(char L) {
    ++ ind;
    p[ind] = p[ind - 1];

    if (fiu[p[ind]][L - 'a'] == -1) {
        ++ n;
        fiu[p[ind]][L - 'a'] = n;
        h[n] = h[p[ind]] + 1;
        for (int i = 0; i < sigma; ++ i)
            fiu[n][i] = -1;

        p[ind] = n;
        ch[n] = L;
        d[n][0] = p[ind - 1];
        for (int i = 1; i < logmax; ++ i) {
            d[n][i] = d[d[n][i - 1]][i - 1];
        }
    } else {
        p[ind] = fiu[p[ind]][L - 'a'];
    }
}

void UndoCommands(int U) {
    ++ ind;
    p[ind] = p[ind - U - 1];
}

char GetLetter(int P) {
    int dif = h[p[ind]] - P - 1;
    int x = p[ind];

    for (int i = logmax - 1; i >= 0; -- i) {
        if (dif & (1 << i))
            x = d[x][i];
    }

    return ch[x];
}

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 3 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 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 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 3 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 640 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 120052 KB Output is correct
2 Correct 785 ms 132024 KB Output is correct
3 Correct 472 ms 128988 KB Output is correct
4 Correct 458 ms 99320 KB Output is correct
5 Correct 580 ms 112100 KB Output is correct
6 Correct 486 ms 142256 KB Output is correct
7 Correct 489 ms 71416 KB Output is correct
8 Correct 479 ms 106900 KB Output is correct
9 Correct 855 ms 146168 KB Output is correct
10 Correct 289 ms 107208 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 103060 KB Output is correct
2 Correct 887 ms 91640 KB Output is correct
3 Correct 444 ms 98860 KB Output is correct
4 Correct 524 ms 72896 KB Output is correct
5 Correct 482 ms 108920 KB Output is correct
6 Correct 489 ms 101416 KB Output is correct
7 Correct 542 ms 108516 KB Output is correct
8 Correct 638 ms 53648 KB Output is correct
9 Correct 953 ms 94936 KB Output is correct
10 Correct 248 ms 106324 KB Output is correct