제출 #511424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511424		tabr	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	441 ms	163956 KiB

scrivener

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

const int N = (int) 1e6 + 10;

char node[N];
int trie[N][26];
int pv[N][20];
int depth[N];
int lg[N];
int id;
int sz;

void Init() {
    node[0] = '!';
    memset(trie, -1, sizeof(trie));
    id = 1;
    sz = 1;
}

void TypeLetter(char ll) {
    int v = lg[id - 1];
    int l = ll - 'a';
    if (trie[v][l] != -1) {
        lg[id] = trie[v][l];
        id++;
        return;
    }
    int to = sz;
    trie[v][l] = to;
    depth[to] = depth[v] + 1;
    lg[id] = to;
    pv[to][0] = v;
    for (int i = 1; i < 20; i++) {
        pv[to][i] = pv[pv[to][i - 1]][i - 1];
    }
    node[to] = ll;
    id++;
    sz++;
}

void UndoCommands(int u) {
    lg[id] = lg[id - 1 - u];
    id++;
}

char GetLetter(int p) {
    int v = lg[id - 1];
    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: 40 / 40