Submission #1024178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024178		socpite	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	246 ms	90540 KiB

scrivener

#include<iostream>
using namespace std;

int n = 0;
const int maxn = 1e6+5;
int st[20][maxn];
char C[maxn];
int dep[maxn], prv[maxn];

void Init() {
	n = 0;
}

void TypeLetter(char L) {
	n++;
	C[n] = L;
	prv[n] = n;
	dep[n] = dep[prv[n-1]] + 1;
	st[0][n] = prv[n-1];
	for(int i = 1; i < 20; i++){
		st[i][n] = st[i-1][st[i-1][n]];
	}
}

void UndoCommands(int U) {
	n++;
	prv[n] = prv[n - U - 1];
}

char GetLetter(int P) {
	int id = prv[n], d = dep[id] - (P + 1);
	for(int i = 0; i < 20; i++){
		if(d&(1<<i))id = st[i][id];
	}
	return C[id];
}

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