제출 #586613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586613		Drew_	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	735 ms	86612 KiB

scrivener

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

const int MAX = 1e6 + 69;
const int LG = 20;

int N = 0;
char ar[MAX];
int len[MAX], par[MAX][LG];

void Init() 
{
    ar[0] = '$';
}

void TypeLetter(char L) 
{
    ++N;
    ar[N] = L; len[N] = len[N-1] + 1; par[N][0] = N-1;
    for (int i = 1; i < LG; ++i)
        par[N][i] = par[par[N][i-1]][i-1];
}

void UndoCommands(int U) 
{
    ++N;
    par[N][0] = par[N-U-1][0]; len[N] = len[N-U-1]; ar[N] = ar[N-U-1];
    for (int i = 1; i < LG; ++i)
        par[N][i] = par[par[N][i-1]][i-1];
}

char GetLetter(int P)
{
    P = len[N] - P - 1;

    int cur = N;
    for (int i = 0; i < LG; ++i)
        if (P >> i & 1)
            cur = par[cur][i];

    return ar[cur];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40