제출 #1370892

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

scrivener

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

namespace {
    constexpr int MAXN = 1000005;
    constexpr int LOG = 20;

    int commandCount;
    int nodeCount;
    int rootAtCommand[MAXN];
    int depthOfNode[MAXN];
    int ancestor[LOG][MAXN];
    unsigned char letterAtNode[MAXN];
}

void Init() {
    commandCount = 0;
    nodeCount = 0;
    rootAtCommand[0] = 0;
    depthOfNode[0] = 0;
    for (int i = 0; i < LOG; ++i) ancestor[i][0] = 0;
}

void TypeLetter(char L) {
    int previousRoot = rootAtCommand[commandCount];
    int node = ++nodeCount;

    letterAtNode[node] = static_cast<unsigned char>(L);
    depthOfNode[node] = depthOfNode[previousRoot] + 1;
    ancestor[0][node] = previousRoot;

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

    rootAtCommand[++commandCount] = node;
}

void UndoCommands(int U) {
    int targetCommand = commandCount - U;
    rootAtCommand[++commandCount] = rootAtCommand[targetCommand];
}

char GetLetter(int P) {
    int node = rootAtCommand[commandCount];
    int steps = depthOfNode[node] - 1 - P;

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

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

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