Submission #761142

#	Time	Username	Problem	Language	Result	Execution time	Memory
761142		SanguineChameleon	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	339 ms	67108 KiB

scrivener

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

const int maxN = 1e6 + 20;
const int maxK = 20;
int par[maxN][maxK];
char a[maxN];
int id[maxN];
int depth[maxN];
int op;
int node;

void Init() {
	op = 1;
	node = 1;
	id[op] = 1;
	depth[node] = 0;
	for (int k = 0; k < maxK; k++) {
		par[1][k] = 1;
	}
}

void TypeLetter(char L) {
	op++;
	node++;
	par[node][0] = id[op - 1];
	depth[node] = depth[id[op - 1]] + 1;
	a[node] = L; 
	for (int k = 1; k < maxK; k++) {
		par[node][k] = par[par[node][k - 1]][k - 1];
	}
	id[op] = node;
}

void UndoCommands(int U) {
	op++;
	id[op] = id[op - 1 - U];
}

char GetLetter(int P) {
	P++;
	int u = id[op];
	int h = depth[u] - P;
	for (int k = 0; k < maxK; k++) {
		if ((h >> k) & 1) {
			u = par[u][k];
		}
	}
	return a[u];
}

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