Submission #31045

#	Time	Username	Problem	Language	Result	Execution time	Memory
31045		14kg	Crayfish scrivener (IOI12_scrivener)	C++11	60 / 100	1000 ms	94868 KiB

scrivener

struct TYPE{
	char num;
	int next_0, lev, next[21];
} d[1000001];
int n, p[21];

void Init(){
    p[0] = 1;
    for (int i = 1; i <= 20; i++) p[i] = p[i - 1] * 2;
}

void TypeLetter(char x){
    n++, d[n].next_0 = n, d[n].num = x, d[n].lev = d[n - 1].lev + 1;
	d[n].next[0] = d[n - 1].next_0;
	for (int i = 1; i <= 20; i++) d[n].next[i] = d[d[n].next[i - 1]].next[i - 1];
}

void UndoCommands(int x) {
    n++, d[n].next_0 = d[n - x - 1].next_0, d[n].lev = d[d[n].next_0].lev;
}

char f(int x, int y){
    if (x != d[x].next_0) return f(d[x].next_0, y);
	if (y == 0) return d[x].num;

	for (int i = 20; i >= 0; i--)
	if (p[i] <= y) return f(d[x].next[i], y - p[i]);
}
char GetLetter(int x){
    return f(n, d[n].lev - x - 1);
}

Compilation message (stderr)

scrivener.cpp: In function 'char f(int, int)':
scrivener.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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