Submission #834787

#	Time	Username	Problem	Language	Result	Execution time	Memory
834787		happypotato	Crayfish scrivener (IOI12_scrivener)	C++17	93 / 100	452 ms	236584 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() {
	// cur = new Trie();
	// function<void(Trie*, int)> build = [&](Trie *cur, int depth) {
	// 	if (depth == -1) return;
	// 	cur->lptr = new Trie(); build(cur->lptr, depth - 1);
	// 	cur->rptr = new Trie(); build(cur->rptr, depth - 1);
	// };
	// // build(cur, 19);
	// ver.pb(cur);
	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++;
}

void UndoCommands(int U) {
	int ptr = (int)(ver.size()) - 1 - U;
	if (ptr == 0) {
		cur = nullptr;
	} else {
		cur = new Trie();
		cur->lptr = ver[ptr]->lptr;
		cur->rptr = ver[ptr]->rptr;
		cur->len = ver[ptr]->len;
	}
	ver.pb(cur);
}
 
char GetLetter(int P) {
	cur = ver.back();
	while (cur->lptr != nullptr && cur->rptr != nullptr) {
		// cerr << cur->len << ' ' << cur->c << endl;
		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: 0 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40