Submission #760652

#	Time	Username	Problem	Language	Result	Execution time	Memory
760652		ymm	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	412 ms	89464 KiB

scrivener

#include <bits/stdc++.h>
#define Loop(x,l,r)  for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;

const int lg = 20;
const int N = 1<<lg;

struct {
	int anc[lg];
	int len;
	char l;
} node[N];
int pos = 0;

void Init() {}

void TypeLetter(char L) {
	int v = pos+1;
	node[v].anc[0] = pos;
	Loop (i,1,lg)
		node[v].anc[i] = node[node[v].anc[i-1]].anc[i-1];
	node[v].len = node[pos].len+1;
	node[v].l = L;
	++pos;
}

void UndoCommands(int U) {
	memcpy(&node[pos+1], &node[pos-U], sizeof(*node));
	++pos;
}

char GetLetter(int P) {
	//string s;
	//for (int v = pos; node[v].l; v = node[v].anc[0])
	//	s += node[v].l;
	//reverse(s.begin(), s.end());
	//cout << s << '\n';
	P = node[pos].len - 1 - P;
	int v = pos;
	LoopR (i,0,lg) {
		if (!(P & (1<<i)))
			continue;
		v = node[v].anc[i];
	}
	return node[v].l;
}

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