Submission #834801

#	Time	Username	Problem	Language	Result	Execution time	Memory
834801		happypotato	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	430 ms	234016 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int flog2(int x) {
	return 31 - __builtin_clz(x);
}
bool ispow2(int x) {
	return (x == (1 << flog2(x)));
}
struct Trie {
	char c;
	int len;
	Trie *lptr, *rptr;
	Trie(char cur = '.'): c(cur), len((cur != '.')), lptr(nullptr), rptr(nullptr) {};
};
vector<Trie*> ver;
Trie *cur, *pre;
void Init() {
	ver.pb(nullptr);
}
 
void TypeLetter(char L) {
	cur = new Trie();
	pre = ver.back();
	ver.pb(cur);
	while (pre != nullptr) {
		cur->len = pre->len + 1;
		if (ispow2(pre->len)) {
			cur->lptr = pre;
			cur->rptr = new Trie(L);
			return;
		}
		cur->lptr = pre->lptr;
		cur->rptr = new Trie();
		cur = cur->rptr;
		pre = pre->rptr;
	}
	cur->c = L;
	cur->len = 1;
}
 
void UndoCommands(int U) {
	int ptr = (int)(ver.size()) - 1 - U;
	ver.pb(ver[ptr]);
}
 
char GetLetter(int P) {
	cur = ver.back();
	while (cur->len != 1) {
		if (P < cur->lptr->len) {
			cur = cur->lptr;
		} else {
			P -= cur->lptr->len;
			cur = cur->rptr;
		}
	}
	return cur->c;
}

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