Submission #130239

#	Time	Username	Problem	Language	Result	Execution time	Memory
130239		khulegub	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1063 ms	6928 KiB

scrivener

#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;

int curr;
vector<pair<char, int> > s; //storing chars and ranks
vector<int> node_par; //storing each node's origin
vector<int> par; //storing each cmd's origin
vector<int> pos; //storing each cmd's position in "s"
void Init() {
	s.pb(mp('#', 0));
	curr = 0; //current node is 0
	pos.pb(0);
	node_par.pb(0);
	par.pb(0); //cmd zero came from zero lol
}
void TypeLetter(char L) {
	par.pb(curr); // new cmd is came from current cmd :v
	s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node
	node_par.pb(pos[curr]);
	pos.pb(s.size() - 1);
	curr++;
}
void UndoCommands(int U) {
	int origin = curr;
	for (int cnt = 1; cnt <= U; cnt++){
		origin = par[origin];
	}
	par.pb(curr);
	curr++;
	pos.pb(pos[origin]);
}
char GetLetter(int P) {
	P++;
	int tmp = pos[curr];
	while( s[tmp].yy > P ){
		tmp = node_par[tmp];
	}
	return s[tmp].xx;
}


// int main(){ //driver-chan
// 	Init();
// 	TypeLetter('a');
// 	cout << GetLetter(0);
// 	TypeLetter('b');
// 	cout << GetLetter(0);
// 	cout << GetLetter(1);
// 	UndoCommands(1);
// 	cout << GetLetter(0);
// 	TypeLetter('c');
// 	cout << GetLetter(1);
// 	// for (auto c : s){
// 	// 	cout << c.yy ;
// 	// }
// 	// cout << s.xx;
// }

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