Submission #1012046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012046		AmirAli_H1	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	611 ms	94548 KiB

scrivener

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 7;
const int maxlg = 20;
int sz; pii p[maxn];
int h[maxn], up[maxn][maxlg];
char A[maxn];

void Init() {
	sz = 1;
}

void TypeLetter(char ch) {
	int v = sz++;
	A[v] = ch; p[v] = Mp(v - 1, 1);
	h[v] = h[p[v].F] + p[v].S;
	up[v][0] = v;
	for (int i = 1; i < maxlg; i++) {
		int u = p[up[v][i - 1]].F;
		up[v][i] = up[u][i - 1];
	}
}

void UndoCommands(int x) {
	int v = sz++;
	A[v] = '.'; p[v] = Mp(v - x - 1, 0);
	h[v] = h[p[v].F] + p[v].S;
	up[v][0] = up[p[v].F][0];
	for (int i = 1; i < maxlg; i++) {
		int u = p[up[v][i - 1]].F;
		up[v][i] = up[u][i - 1];
	}
}

char GetLetter(int x) {
	int v = sz - 1; x = (h[v] - x);
	while (x > 0) {
		int j = __builtin_ctz(x);
		v = up[v][j]; x ^= (1 << j);
		if (x != 0) v = p[v].F;
	}
	return A[v];
}

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