제출 #1370875

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

scrivener

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

namespace {
    constexpr int MAX_OPS = 1000000 + 5;
    constexpr int LOG = 21;

    int commandCount;
    int nodeCount;
    int currentNode;
    int currentLength;

    vector<array<int, LOG>> up;
    vector<char> letter;
    vector<int> versionNode;
    vector<int> versionLength;
}

void Init() {
    commandCount = 0;
    nodeCount = 0;
    currentNode = 0;
    currentLength = 0;

    up.assign(1, {});
    letter.assign(1, 0);

    versionNode.assign(1, 0);
    versionLength.assign(1, 0);
}

void TypeLetter(char L) {
    ++nodeCount;

    array<int, LOG> jumps{};
    jumps[0] = currentNode;
    for (int i = 1; i < LOG; ++i) {
        jumps[i] = up[jumps[i - 1]][i - 1];
    }

    up.push_back(jumps);
    letter.push_back(L);

    currentNode = nodeCount;
    ++currentLength;

    ++commandCount;
    versionNode.push_back(currentNode);
    versionLength.push_back(currentLength);
}

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

    currentNode = versionNode[target];
    currentLength = versionLength[target];

    ++commandCount;
    versionNode.push_back(currentNode);
    versionLength.push_back(currentLength);
}

char GetLetter(int P) {
    int steps = currentLength - 1 - P;
    int node = currentNode;

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

    return letter[node];
}

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