Submission #153042

# Submission time Handle Problem Language Result Execution time Memory
153042 2019-09-11T15:08:11 Z popovicirobert Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
1000 ms 145564 KB
#include <bits/stdc++.h>

using namespace std;

static const int MAXN = (int) 1e6;

static int anc_let[MAXN + 1][20], anc[MAXN + 1][20];
static int len[MAXN + 1], cur, sz;
static char let[MAXN + 1];

void Init() {
    cur = sz = 0;
    len[0] = 0;
}

void TypeLetter(char L) {
    sz++;
    let[sz] = L;
    len[sz] = len[cur] + 1;

    anc_let[sz][0] = cur;
    anc[sz][0] = cur;

    for(int bit = 1; bit < 20; bit++) {
        anc[sz][bit] = anc[anc[sz][bit - 1]][bit - 1];
        anc_let[sz][bit] = anc_let[anc_let[sz][bit - 1]][bit - 1];
    }

    cur = sz;
}

void UndoCommands(int U) {
    int last = cur;
    for(int bit = 0; bit < 20; bit++) {
        if(U & (1 << bit)) {
            cur = anc[cur][bit];
        }
    }
    sz++;
    let[sz] = let[cur];
    len[sz] = len[cur];

    cur = anc_let[cur][0];

    anc[sz][0] = last;
    anc_let[sz][0] = cur;

    for(int bit = 1; bit < 20; bit++) {
        anc[sz][bit] = anc[anc[sz][bit - 1]][bit - 1];
        anc_let[sz][bit] = anc_let[anc_let[sz][bit - 1]][bit - 1];
    }

    cur = sz;
}

char GetLetter(int P) {
    int ans = cur;
    P = len[cur] - P - 1;
    for(int bit = 0; bit < 20; bit++) {
        if(P & (1 << bit)) {
            ans = anc_let[ans][bit];
        }
    }
    return let[ans];
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 4 ms 1016 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 5 ms 1144 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 861 ms 119480 KB Output is correct
2 Execution timed out 1044 ms 145564 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 981 ms 110400 KB Output is correct
2 Correct 890 ms 96616 KB Output is correct
3 Correct 952 ms 121952 KB Output is correct
4 Correct 918 ms 107552 KB Output is correct
5 Correct 760 ms 140536 KB Output is correct
6 Correct 827 ms 145092 KB Output is correct
7 Correct 789 ms 144964 KB Output is correct
8 Execution timed out 1089 ms 108152 KB Time limit exceeded
9 Halted 0 ms 0 KB -