Submission #1243596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243596		badge881	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	741 ms	83816 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char ch;
    int depth;
    vector<int> ancestors;
};

vector<Node> buffer;
vector<int> state;

void Init() {
    ;
}

int findAncestor(int idx, int target_depth) {
    int delta = buffer[idx].depth - target_depth;
    int step = 0;
    while (delta > 0) {
        ++step;
        delta /= 2;
    }
    return (buffer[idx].depth == target_depth)
           ? idx
           : findAncestor(buffer[idx].ancestors[step - 1], target_depth);
}

void TypeLetter(char c) {
    if (state.empty() || state.back() == -1) {
        buffer.push_back({c, 0, {}});
    } else {
        int parent = state.back();
        int new_depth = buffer[parent].depth + 1;
        vector<int> links;
        links.push_back(parent);
        while (links.size() < buffer[parent].ancestors.size() + 1) {
            parent = buffer[parent].ancestors[links.size() - 1];
            links.push_back(parent);
        }
        buffer.push_back({c, new_depth, links});
    }
    state.push_back((int)buffer.size() - 1);
}

void UndoCommands(int k) {
    if (k == state.size()) {
        state.push_back(-1);
    } else {
        int restored = state[state.size() - 1 - k];
        state.push_back(restored);
    }
}

char GetLetter(int pos) {
    int idx = findAncestor(state.back(), pos);
    return buffer[idx].ch;
}

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