Submission #411433

#	Time	Username	Problem	Language	Result	Execution time	Memory
411433		KoD	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	558 ms	101320 KiB

scrivener

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct Node {
    char written;
    int depth;
    std::array<int, 20> parent;
};

Vec<int> at;
Vec<Node> node;

void Init() {
    at.push_back(0);
    std::array<int, 20> tmp;
    tmp.fill(0);
    node.push_back(Node{'$', 0, tmp});
}

void TypeLetter(char L) {
    std::array<int, 20> tmp;
    tmp[0] = at.back();
    for (int i = 1; i < 20; ++i) {
        tmp[i] = node[tmp[i - 1]].parent[i - 1];
    }
    node.push_back(Node{L, node[at.back()].depth + 1, tmp});
    at.push_back(node.size() - 1);
}

void UndoCommands(int U) {
    at.push_back(at[at.size() - U - 1]);
}

char GetLetter(int P) {
    int u = at.back();
    int len = node[u].depth - P - 1;
    for (int i = 0; i < 20; ++i) {
        if (len >> i & 1) {
            u = node[u].parent[i];
        }
    }
    return node[u].written;
}

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