Submission #393037

#	Time	Username	Problem	Language	Result	Execution time	Memory
393037		rainboy	Crayfish scrivener (IOI12_scrivener)	C11	100 / 100	586 ms	67256 KiB

scrivener

#define N	1000001
#define LN	19	/* LN = floor(log2(N)) */

int uu[N], pp[N][LN + 1], dd[N], n_, i; char cc[N];

void Init() {
	n_ = 1;
}

void TypeLetter(char c) {
	int l, u;

	i++;
	u = uu[i] = n_++;
	cc[u] = c, pp[u][0] = uu[i - 1], dd[u] = dd[uu[i - 1]] + 1;
	for (l = 1; 1 << l <= dd[u]; l++)
		pp[u][l] = pp[pp[u][l - 1]][l - 1];
}

void UndoCommands(int k) {
	i++, uu[i] = uu[i - 1 - k];
}

char GetLetter(int d) {
	int u = uu[i], l;

	d++;
	for (l = LN; l >= 0; l--)
		if (dd[u] - d >= 1 << l)
			u = pp[u][l];
	return cc[u];
}

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