Submission #586613

#	Time	Username	Problem	Language	Result	Execution time	Memory
586613		Drew_	Crayfish scrivener (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