Submission #239579

#	Time	Username	Problem	Language	Result	Execution time	Memory
239579		Coroian_David	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	605 ms	90616 KiB

scrivener

#include <bits/stdc++.h>

#define MAX_N 1000000
#define MAX_P2 19

using namespace std;

int k;
int ant[MAX_N + 1][MAX_P2 + 1];
int stk[MAX_N + 1];
int d[MAX_N + 1];
char chr[MAX_N + 1];

void Init()
{

}

void TypeLetter(char L)
{
    k ++;
    ant[k][0] = stk[k - 1];
    stk[k] = k;
    chr[k] = L;
    d[k] = d[ant[k][0]] + 1;

    for(int p2 = 1; p2 <= 19; p2 ++)
        ant[k][p2] = ant[ant[k][p2 - 1]][p2 - 1];
}

void UndoCommands(int U)
{
    k ++;
    stk[k] = stk[k - 1 - U];
}

char GetLetter(int P)
{
    P ++;

    int len = d[stk[k]] - P;

    int cr = stk[k];
    for(int i = 0; i <= 19; i ++)
    {
        if(((1 << i) & len) != 0)
            cr = ant[cr][i];
    }

    return chr[cr];
}

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