Submission #834764

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

scrivener

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct Trie {
	char c;
	int len;
	Trie *nxt[4];
	Trie(char cur = '.'): c(cur), len(0) {
		for (int i = 0; i < 4; i++) nxt[i] = nullptr;
	};
};
vector<Trie*> ver;
int cnt = 0;
Trie *cur, *pre;
void Init() {
	cur = new Trie();
	cnt++;
	function<void(Trie*, int)> build = [&](Trie *cur, int depth) {
		if (depth < 0) return;
		for (int i = 0; i < 4; i++) {
			cur->nxt[i] = new Trie();
			build(cur->nxt[i], depth - 2);
		}
		cnt += 4;
	};
	build(cur, 18);
	ver.pb(cur);
}

void TypeLetter(char L) {
	cur = new Trie();
	cnt++;
	pre = ver.back();
	ver.pb(cur);
	for (int i = 18; i >= 0; i -= 2) {
		cur->len = pre->len;
		int tar = cur->len++;
		for (int j = 0; j < 4; j++) {
			cur->nxt[j] = pre->nxt[j];
		}
		int dest = ((tar >> i) & 3);
		pre = cur->nxt[dest];
		cur->nxt[dest] = new Trie();
		cur = cur->nxt[dest];
		cnt++;
	}
	cur->c = L;
}

void UndoCommands(int U) {
	cur = new Trie();
	cnt++;
	int ptr = (int)(ver.size()) - 1 - U;
	for (int i = 0; i < 4; i++) {
		cur->nxt[i] = ver[ptr]->nxt[i];
	}
	cur->len = ver[ptr]->len;
	ver.pb(cur);
}

char GetLetter(int P) {
	cur = ver.back();
	for (int i = 18; i >= 0; i -= 2) {
		int dest = ((P >> i) & 3);
		cur = cur->nxt[dest];
	}
	// 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