Submission #153045

#	Time	Username	Problem	Language	Result	Execution time	Memory
153045		popovicirobert	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	987 ms	86844 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

static const int MAXN = (int) 1e6;

static int anc_let[20][MAXN + 1];
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[0][sz] = cur;

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

    cur = sz;
}

void UndoCommands(int U) {
    cur -= U;
    sz++;
    let[sz] = let[cur];
    len[sz] = len[cur];

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

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

    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[bit][ans];
        }
    }
    return let[ans];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40