Submission #370501

#	Time	Username	Problem	Language	Result	Execution time	Memory
370501		ijxjdjd	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	635 ms	102252 KiB

scrivener

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = (int)(1e6) + 5;
const int MAXK = 21;

int up[MAXN][MAXK];
int undo[MAXN][MAXK];
int depth[MAXN];
char res[MAXN];
int cnt = 1;
int liftUp(int u, int d) {
    for (int i = 0; i < MAXK; i++) {
        if (d&(1<<i)) {
            u = up[u][i];
        }
    }
    return u;
}
int liftUndo(int u, int d) {
    for (int i = 0; i < MAXK; i++) {
        if (d&(1<<i)) {
            u = undo[u][i];
        }
    }
    return u;
}
void Init() {

}

void TypeLetter(char L) {
    res[cnt] = L;
    up[cnt][0] = cnt-1;
    undo[cnt][0] = cnt-1;
    for (int i = 1; i < MAXK; i++) {
        up[cnt][i] = up[up[cnt][i-1]][i-1];
        undo[cnt][i] = undo[undo[cnt][i-1]][i-1];
    }
    depth[cnt] = depth[cnt-1];
    cnt++;
}

void UndoCommands(int U) {
    int next = liftUndo(cnt-1, U);
    res[cnt] = res[next];
    up[cnt][0] = up[next][0];
    undo[cnt][0] = cnt-1;
    for (int i = 1; i < MAXK; i++) {
        up[cnt][i] = up[up[cnt][i-1]][i-1];
        undo[cnt][i] = undo[undo[cnt][i-1]][i-1];
    }
    depth[cnt] = depth[next];
}
char GetLetter(int P) {
    return  res[liftUp(cnt-1, depth[cnt-1] - P - 1)];
}

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