Submission #418351

#	Time	Username	Problem	Language	Result	Execution time	Memory
418351		Aldas25	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	549 ms	151488 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;

const int MAXK = 25;
const int MAXN = 1e6+100;

int cnt = 0;
int ch[MAXN][26];
char letter[MAXN];
int lift[MAXN][MAXK];
int dep[MAXN];

int initNode (char c) {
    letter[cnt] = c;
    FOR(i, 0, 25) ch[cnt][i] = -1;

    cnt++;
    return cnt-1;
}

void buildLift (int id) {
    FOR(i, 1, MAXK-1)
        lift[id][i] = lift[lift[id][i-1]][i-1];
}

int addNode (int id, char c) {
    int letId = c-'a';
    if (ch[id][letId] == -1) {
        int chId = initNode(c);
        ch[id][letId] = chId;
        lift[chId][0] = id;
        buildLift(chId);
        dep[chId] = dep[id]+1;
    }
    return ch[id][letId];
}

int lft (int id, int d) {
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            id = lift[id][i];
    return id;
}

int curId;
int timeToNode [MAXN];

void Init() {
    curId = 0;
    timeToNode[curId] = initNode('a');
    dep[curId] = -1;
}

void TypeLetter(char L) {
    timeToNode[curId+1] = addNode(timeToNode[curId], L);
    curId++;
}

void UndoCommands(int U) {
    timeToNode[curId+1] = timeToNode[curId-U];
    curId++;
    //printCur();
}

char GetLetter(int P) {
    int nodeId = lft (timeToNode[curId], dep[timeToNode[curId]]-P);
    return letter[nodeId];
}

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