제출 #511410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511410		tabr	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	0 / 100	1 ms	680 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);
}

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);
    return 0;
}
#endif

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