제출 #1370873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370873		gptgpt	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	333 ms	18488 KiB

scrivener

namespace {
constexpr int MAX_CALLS = 1000000;
constexpr int BASE = 32;
constexpr int LEVELS = 4;

int up[MAX_CALLS + 5][LEVELS];
int depth_node[MAX_CALLS + 5];
int version_root[MAX_CALLS + 5];
unsigned char node_char[MAX_CALLS + 5];

int node_count = 0;
int command_count = 0;
}

void Init() {
    node_count = 0;
    command_count = 0;
    version_root[0] = 0;
    depth_node[0] = 0;
    node_char[0] = 0;
    for (int i = 0; i < LEVELS; ++i) up[0][i] = 0;
}

void TypeLetter(char L) {
    int parent = version_root[command_count];
    ++node_count;

    node_char[node_count] = static_cast<unsigned char>(L);
    depth_node[node_count] = depth_node[parent] + 1;
    up[node_count][0] = parent;

    for (int j = 1; j < LEVELS; ++j) {
        int a = node_count;
        for (int k = 0; k < BASE; ++k) {
            a = up[a][j - 1];
        }
        up[node_count][j] = a;
    }

    ++command_count;
    version_root[command_count] = node_count;
}

void UndoCommands(int U) {
    int root = version_root[command_count - U];
    ++command_count;
    version_root[command_count] = root;
}

char GetLetter(int P) {
    int node = version_root[command_count];
    if (node == 0) return 0;

    int steps = depth_node[node] - 1 - P;
    if (steps < 0) return 0;

    for (int j = 0; j < LEVELS; ++j) {
        int digit = steps % BASE;
        steps /= BASE;
        for (int k = 0; k < digit; ++k) {
            node = up[node][j];
        }
    }

    return static_cast<char>(node_char[node]);
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 7 / 7
• 서브태스크 3: 22 / 22
• 서브태스크 4: 26 / 26
• 서브태스크 5: 40 / 40