Submission #760684

#	Time	Username	Problem	Language	Result	Execution time	Memory
760684		NothingXD	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	319 ms	90396 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

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

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e6 + 10;
const int lg = 20;

int n, cur, h[maxn], idx[maxn], par[maxn][lg];
string s;

void Init() {
	memset(par, -1, sizeof par);
	idx[0] = -1;
}

void TypeLetter(char L){
	s.push_back(L);
	int v = s.size()-1;
	if (idx[n] == -1){
		h[v] = 0;
	}
	else{
		h[v] = h[idx[n]] + 1;
	}
	par[v][0] = idx[n];
	for (int i = 1; i < lg; i++){
		if (par[v][i-1] != -1) par[v][i] = par[par[v][i-1]][i-1];
	}
	n++;
	idx[n] = v;
}

void UndoCommands(int U) {
	idx[n+1] = idx[n-U];
	n++;
}

char GetLetter(int P) {
	int v = idx[n];
	int x = h[v] - P;
	for (int i = 0; i < lg; i++) if ((x >> i) & 1) v = par[v][i];
	return s[v];
}

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