제출 #1370889

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

scrivener

const int MAX_CALLS = 1000000 + 5;
const int LOG = 20;

static int up[MAX_CALLS][LOG];
static int versionTail[MAX_CALLS];
static int versionLen[MAX_CALLS];
static char nodeChar[MAX_CALLS];

static int commandCount;
static int nodeCount;

void Init() {
    commandCount = 0;
    nodeCount = 0;
    versionTail[0] = 0;
    versionLen[0] = 0;
}

void TypeLetter(char L) {
    int currentTail = versionTail[commandCount];

    ++nodeCount;
    nodeChar[nodeCount] = L;
    up[nodeCount][0] = currentTail;

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

    ++commandCount;
    versionTail[commandCount] = nodeCount;
    versionLen[commandCount] = versionLen[commandCount - 1] + 1;
}

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

    ++commandCount;
    versionTail[commandCount] = versionTail[target];
    versionLen[commandCount] = versionLen[target];
}

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

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

    return nodeChar[node];
}

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