Submission #773004

#	Time	Username	Problem	Language	Result	Execution time	Memory
773004		penguin133	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	689 ms	90544 KiB

scrivener

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

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void Init() {}
int par[21][1000005], cur, dep[1000005];
char stuf[1000005];
void TypeLetter(char L) {
	stuf[++cur] = L;
	dep[cur] = dep[cur - 1] + 1;
	par[0][cur] = cur - 1;
	for(int i = 1; i <= 20; i++)par[i][cur] = par[i-1][par[i-1][cur]];
}

void UndoCommands(int U) {
	cur++;
	dep[cur] = dep[cur - U - 1];
	stuf[cur] = stuf[cur - U - 1];
	par[0][cur] = par[0][cur - U - 1];
	for(int i = 1; i <= 20; i++)par[i][cur] = par[i-1][par[i-1][cur]];
}

char GetLetter(int P) {
	int brr = dep[cur] - P - 1;
	int tmp = cur;
	for(int i = 20; i >= 0; i--)if(brr >> i & 1)tmp = par[i][tmp];
	//cout << cur << ' ' << tmp << ' ' << dep[cur] << ' ' << '\n';
	return stuf[tmp];
}

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