Submission #1186594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186594		Nonoze	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	610 ms	202320 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x).size()

struct trie {
	int next[26], sz;
	char ch;
	vector<int> up;
	trie() {
		memset(next, -1, sizeof(next));
		ch=0, sz=0;
	}
};

vector<trie*> tries;
vector<int> empls;


void Init() {
	tries.pb(new trie());
	empls.pb(0);
}

void TypeLetter(char L) {
	int act = empls.back();
	if (tries[act]->next[L-'a']!=-1) {
		empls.pb(tries[act]->next[L-'a']);
		return;
	}
	tries[act]->next[L-'a'] = sz(tries);
	tries.pb(new trie()), empls.pb(sz(tries)-1); tries.back()->ch=L, tries.back()->sz=tries[act]->sz+1;
	trie *cur=tries.back();
	cur->up.pb(act);
	for (int j=1; j<20; j++) {
		if (sz(tries[cur->up[j-1]]->up)<j) break;
		cur->up.pb(tries[cur->up[j-1]]->up[j-1]);
	}
}

void UndoCommands(int U) {
	empls.pb(empls[sz(empls)-U-1]);
}

char GetLetter(int P) {
	int act=empls.back();
	int k=tries[act]->sz-P-1;
	for (int j=0; j<20; j++) {
		if ((k&(1<<j))) {
			act=tries[act]->up[j];
		}
	}
	return tries[act]->ch;
}

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