Submission #518686

#	Time	Username	Problem	Language	Result	Execution time	Memory
518686		sliviu	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	422 ms	85564 KiB

scrivener

#include <bits/stdc++.h>

int nr;
struct state {
	char letter;
	int length, p[20];
} s[1000001];

void Init() {}

void TypeLetter(char L) {
	s[nr + 1] = {L,s[nr].length + 1, nr};
	++nr;
	for (int i = 1; i < 20; ++i)
		s[nr].p[i] = s[s[nr].p[i - 1]].p[i - 1];
}

void UndoCommands(int U) {
	s[nr + 1] = s[nr - U];
	++nr;
}

char GetLetter(int P) {
	int cur = nr;
	P = s[cur].length - 1 - P;
	for (int i = 0; i < 20; ++i)
		if (P & (1 << i))
			cur = s[cur].p[i];
	return s[cur].letter;
}

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