Submission #123457

#	Time	Username	Problem	Language	Result	Execution time	Memory
123457		turbat	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	618 ms	94456 KiB

scrivener

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

char last, s[N];
int t[N][21], now, d[N], f[N];

void Init() {}

void TypeLetter(char L) {
	now++;
	s[now] = L;
	f[now] = now;
	d[now] = d[f[now - 1]] + 1;
	t[now][0] = f[now - 1];
	for (int i = 1;i < 21;i++)
		t[now][i] = t[t[now][i - 1]][i - 1];
}

void UndoCommands(int U) {
	now++;
	f[now] = f[now - U - 1];
}

char GetLetter(int P) {
	int a = d[f[now]] - P - 1, cur = f[now];
	for (int i = 0;i < 21;i++)
		if (a & 1<<i)
			cur = t[cur][i];
	return s[cur];
}

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