Submission #335599

#	Time	Username	Problem	Language	Result	Execution time	Memory
335599		Joshc	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	583 ms	93932 KiB

scrivener

#include <vector>
using namespace std;

struct node {
    char letter;
    int ancestors[20];
    int depth;
};

node history[1000001];
int moves = 0;

void Init() {
    history[0].depth = 0;
    for (int i=0; i<1000001; i++) {
        for (int j=0; j<20; j++) history[i].ancestors[j] = -1;
    }
}

void TypeLetter(char L) {
    moves++;
    history[moves].letter = L;
    history[moves].depth = history[moves-1].depth+1;
    history[moves].ancestors[0] = moves-1;
    for (int i=1; i<20; i++) {
        if (history[history[moves].ancestors[i-1]].ancestors[i-1] == -1) break;
        history[moves].ancestors[i] = history[history[moves].ancestors[i-1]].ancestors[i-1];
    }
}

void UndoCommands(int U) {
    moves++;
    history[moves] = history[moves-U-1];
}

char GetLetter(int P) {
    node ans = history[moves];
    for (int i=0; i<20; i++) {
        if ((history[moves].depth-P-1)&(1<<i)) ans = history[ans.ancestors[i]];
    }
    return ans.letter;
}

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