Submission #17133

#	Time	Username	Problem	Language	Result	Execution time	Memory
17133		murat	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	454 ms	183356 KiB

scrivener

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40