Submission #379346

#	Time	Username	Problem	Language	Result	Execution time	Memory
379346		pavement	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	610 ms	112620 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

int anc[1000005][25], ver[1000005], dep[1000005], cur;
char val[1000005];

void Init() {
	memset(anc, -1, sizeof anc);
}

void TypeLetter(char L) {
	cur++;
	val[cur] = L;
	ver[cur] = cur;
	if (cur > 1) anc[cur][0] = ver[cur - 1], dep[cur] = dep[ver[cur - 1]] + 1;
	for (int i = 1; i <= 20; i++)
		if (anc[cur][i - 1] != -1)
			anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
}

void UndoCommands(int U) {
	cur++;
	ver[cur] = ver[cur - U - 1];
}

int get_anc(int n, int k) {
	int d = dep[n] - k;
	for (int i = 0; d > 0; i++, d >>= 1)
		if (d & 1) n = anc[n][i];
	return val[n];
}

char GetLetter(int P) {
	return get_anc(ver[cur], P);
}

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