제출 #1370885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370885		gptgpt	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	100 / 100	209 ms	62780 KiB

scrivener

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

int up[MAX_CALLS][LOG];
int depthArr[MAX_CALLS];
char valueArr[MAX_CALLS];
int historyRoot[MAX_CALLS];

int nodeCount;
int commandCount;
int currentRoot;
}

void Init() {
    nodeCount = 0;
    commandCount = 0;
    currentRoot = 0;
    historyRoot[0] = 0;
    depthArr[0] = 0;
    valueArr[0] = '\0';
    for (int i = 0; i < LOG; ++i) up[0][i] = 0;
}

void TypeLetter(char L) {
    int v = ++nodeCount;
    valueArr[v] = L;
    depthArr[v] = depthArr[currentRoot] + 1;
    up[v][0] = currentRoot;

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

    currentRoot = v;
    historyRoot[++commandCount] = currentRoot;
}

void UndoCommands(int U) {
    currentRoot = historyRoot[commandCount - U];
    historyRoot[++commandCount] = currentRoot;
}

char GetLetter(int P) {
    int v = currentRoot;
    int steps = depthArr[v] - 1 - P;

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

    return valueArr[v];
}

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