Submission #511415

#	Time	Username	Problem	Language	Result	Execution time	Memory
511415		tabr	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1018 ms	186944 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

string node;
vector<vector<int>> trie;
vector<vector<int>> pv;
vector<int> depth;
vector<int> lg;

void Init() {
    node += "!";
    trie.emplace_back(vector<int>(26, -1));
    pv.emplace_back(vector<int>(20, 0));
    depth.emplace_back(0);
    lg.emplace_back(0);
}

void TypeLetter(char ll) {
    int v = lg.back();
    int l = ll - 'a';
    if (trie[v][l] != -1) {
        lg.emplace_back(trie[v][l]);
        return;
    }
    int to = (int) node.size();
    trie[v][l] = to;
    trie.emplace_back(vector<int>(26, -1));
    pv.emplace_back(vector<int>(20, 0));
    depth.emplace_back(depth[v] + 1);
    lg.emplace_back(to);
    pv[to][0] = v;
    for (int i = 1; i < 20; i++) {
        pv[to][i] = pv[pv[to][i - 1]][i - 1];
    }
    node += ll;
}

void UndoCommands(int u) {
    lg.emplace_back(lg.rbegin()[u]);
}

char GetLetter(int p) {
    int v = lg.back();
    int up = depth[v] - 1 - p;
    for (int i = 19; i >= 0; i--) {
        if (up & (1 << i)) {
            v = pv[v][i];
        }
    }
    return node[v];
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Init();
    TypeLetter('a');
    TypeLetter('b');
    cout << GetLetter(1) << '\n';
    TypeLetter('d');
    UndoCommands(2);
    UndoCommands(1);
    cout << GetLetter(2) << '\n';
    TypeLetter('e');
    UndoCommands(1);
    UndoCommands(5);
    TypeLetter('c');
    cout << GetLetter(2) << '\n';
    UndoCommands(2);
    cout << GetLetter(2) << '\n';
    return 0;
}
#endif

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