Submission #760804

#	Time	Username	Problem	Language	Result	Execution time	Memory
760804		Sohsoh84	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	363 ms	90552 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 1e6 + 10;
const ll LOG = 20;

vector<int> vec;
int cur, par[MAXN][LOG], H[MAXN];
char F[MAXN];

void Init() {
	cur = 0;
	vec.push_back(cur);
}

void TypeLetter(char L) {
	int v = int(vec.size());
	F[v] = L;
	H[v] = H[cur] + 1;

	par[v][0] = cur;
	cur = v;
	vec.push_back(cur);

	for (int i = 1; i < LOG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
}

void UndoCommands(int U) {
	cur = vec[int(vec.size()) - 1 - U];
	vec.push_back(cur);
}

char GetLetter(int P) {
	int k = H[cur] - P - 1;
	int v = cur;

	for (int i = 0; i < LOG; i++)
		if (k >> i & 1)
			v = par[v][i];

	return F[v];
}

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