Submission #1056841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056841		lovrot	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	184 ms	65360 KiB

scrivener

#include <cstdio>

#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

const int LOG = 20;
const int N = 1 << LOG;

char c[N]; // = {'*'};
int nov = 1, up[N][LOG], dep[N], pos[N], lst;

char climb(int u, int x) { 
	for(int i = LOG - 1; i >= 0; --i) { 
		if(x & (1 << i)) { 
			u = up[u][i];
		}
	}
	return c[u];
}

void Init() {}

void TypeLetter(char L) {
	up[nov][0] = pos[lst];	
	for(int i = 1; i < LOG; ++i) { 
		up[nov][i] = up[up[nov][i - 1]][i - 1]; 
	}

	dep[nov] = dep[pos[lst]] + 1;
	c[nov] = L;
	pos[++lst] = nov++;
}

void UndoCommands(int U) {
	++lst;
	pos[lst] = pos[lst - U - 1];	
}

char GetLetter(int P) {
	return climb(pos[lst], dep[pos[lst]] - P - 1);
}

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