제출 #1370872

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

scrivener

#include <cstddef>

namespace {
    constexpr int MAX_CALLS = 1000000 + 5;
    constexpr int LOG = 20;

    int up[MAX_CALLS][LOG];
    char letterValue[MAX_CALLS];

    int versionRoot[MAX_CALLS];
    int versionLength[MAX_CALLS];

    int nodeCount;
    int commandCount;
    int currentRoot;
    int currentLength;
}

void Init() {
    nodeCount = 0;
    commandCount = 0;
    currentRoot = 0;
    currentLength = 0;
    versionRoot[0] = 0;
    versionLength[0] = 0;
}

void TypeLetter(char L) {
    ++nodeCount;
    letterValue[nodeCount] = L;

    up[nodeCount][0] = currentRoot;
    for (int i = 1; i < LOG; ++i) {
        up[nodeCount][i] = up[up[nodeCount][i - 1]][i - 1];
    }

    currentRoot = nodeCount;
    ++currentLength;

    ++commandCount;
    versionRoot[commandCount] = currentRoot;
    versionLength[commandCount] = currentLength;
}

void UndoCommands(int U) {
    int target = commandCount - U;

    currentRoot = versionRoot[target];
    currentLength = versionLength[target];

    ++commandCount;
    versionRoot[commandCount] = currentRoot;
    versionLength[commandCount] = currentLength;
}

char GetLetter(int P) {
    if (P < 0 || P >= currentLength) {
        return 0;
    }

    int v = currentRoot;
    int steps = currentLength - 1 - P;

    for (int i = 0; i < LOG; ++i) {
        if (steps & (1 << i)) {
            v = up[v][i];
        }
    }

    return letterValue[v];
}

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