Submission #7276

#	Time	Username	Problem	Language	Result	Execution time	Memory
7276		myungwoo	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	684 ms	130332 KiB

scrivener

#include <stdlib.h>
#include <stdio.h>

#define MAXK 1000006

static int K;

static struct STATE{
    int len;
    char letter;
    STATE *prev[20];
} *state[MAXK];

void Init() {}

STATE *make(int len, char letter, STATE *prev)
{
    STATE *ret=(STATE*)malloc(sizeof(STATE));
    ret->len = len; ret->letter = letter;
    for (int i=0;i<20;i++) ret->prev[i] = NULL;
    ret->prev[0] = prev;
    for (int i=0;i<19&&ret->prev[i];i++){
        ret->prev[i+1] = ret->prev[i]->prev[i];
    }
    return ret;
}

void TypeLetter(char letter)
{
    STATE *tmp;
    if (state[K]) tmp = make(state[K]->len+1,letter,state[K]);
    else tmp = make(1,letter,NULL);
    state[++K] = tmp;
}

void UndoCommands(int steps)
{
    state[++K] = state[K-steps-1];
}

char GetLetter(int pos)
{
    STATE *now=state[K];
    int bef=now->len-pos-1,i;
    for (i=20;i--;) if ((bef>>i)&1){
        now = now->prev[i];
    }
    return now->letter;
}

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