Submission #594910

#	Time	Username	Problem	Language	Result	Execution time	Memory
594910		8e7	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	331 ms	67968 KiB

scrivener

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
int pos[maxn], len[maxn], anc[20][maxn];
char c[maxn];
int ti = 1, st = 0;

void Init() {}

void TypeLetter(char L) {
	int prv = pos[ti-1];
	st++;
	anc[0][st] = prv;
	for (int i = 1;i < 20;i++) anc[i][st] = anc[i-1][anc[i-1][st]];
	len[ti] = len[ti-1] + 1;
	pos[ti] = st;
	c[st] = L;
	ti++;
}

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

char GetLetter(int P) {
	int dis = len[ti-1] - P - 1;
	
	int cur = pos[ti-1], cnt = 0;
	while (dis) {
		if (dis & 1) cur = anc[cnt][cur];
		cnt++, dis >>= 1;
	}
	return c[cur];
}

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