Submission #834768

#	Time	Username	Problem	Language	Result	Execution time	Memory
834768		happypotato	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	398 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct Trie {
	char c;
	int len;
	Trie *lptr, *rptr;
	Trie(char cur = '.'): c(cur), len(0), lptr(nullptr), rptr(nullptr) {};
};
vector<Trie*> ver;
int cnt = 0;
Trie *cur, *pre;
Trie *EMPTY = new Trie();
void Init() {
	cur = new Trie();
	cnt++;
	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);
		cnt += 2;
	};
	// build(cur, 19);
	ver.pb(cur);
}
 
void TypeLetter(char L) {
	cur = new Trie();
	cnt++;
	pre = ver.back();
	ver.pb(cur);
	for (int i = 19; i >= 0; i--) {
		if (pre == nullptr) pre = EMPTY;
		cur->len = pre->len;
		int tar = cur->len++;
		cur->lptr = pre->lptr;
		cur->rptr = pre->rptr;
		if (!bool(tar & (1 << i))) {
			pre = cur->lptr;
			cur->lptr = new Trie();
			cur = cur->lptr;
		} else {
			pre = cur->rptr;
			cur->rptr = new Trie();
			cur = cur->rptr;
		}
		cnt++;
	}
	cur->c = L;
}
 
void UndoCommands(int U) {
	cur = new Trie();
	cnt++;
	int ptr = (int)(ver.size()) - 1 - U;
	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();
	for (int i = 19; i >= 0; i--) {
		if (!bool(P & (1 << i))) {
			cur = cur->lptr;
		} else {
			cur = cur->rptr;
		}
	}
	// cerr << cnt << endl;
	return cur->c;
}

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