Submission #601873

#	Time	Username	Problem	Language	Result	Execution time	Memory
601873		acatmeowmeow	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	455 ms	81052 KiB

scrivener

//#include "grader.h"

#include <bits/stdc++.h>

using namespace std;

//#define int long long

const int N = 1e6 + 5, LG = 20;
int vertex = 0, cur_vertex = 0, depth[N], lift[N][LG + 5];
char mp[N];
vector<int> command;

void Init() {
	mp[0] = '\0', command.push_back(0);
	for (int i = 0; i <= LG; i++) lift[0][i] = 0;
}

void TypeLetter(char L) {
	vertex++;
	int u = cur_vertex, v = vertex;
	mp[v] = L;
	depth[v] = depth[u] + 1;
	lift[v][0] = u;
	for (int i = 1; i <= LG; i++) lift[v][i] = lift[lift[v][i - 1]][i - 1];
	command.push_back(v);
	cur_vertex = v;
}

void UndoCommands(int U) {
	int sz = command.size() - 1;
	cur_vertex = command[sz - U];
	command.push_back(cur_vertex);
}

bool set_bit(int mask, int k) { return mask & (1ll << k); }

char GetLetter(int P) {
	int u = cur_vertex, jump = depth[u] - P - 1;
	for (int i = 0; i <= LG; i++) {
		if (!set_bit(jump, i)) continue;
		u = lift[u][i];
	}
	return mp[u];
}

/*signed main() {
	Init();
	while (true) {
		int type;
		cin >> type;
		if (type == 1) {
			char ch;
			cin >> ch;
			TypeLetter(ch);
		} else if (type == 2) {
			int u;
			cin >> u;
			UndoCommands(u);
		} else if (type == 3){
			int u;
			cin >> u;
			cout << GetLetter(u) << endl;
		} else break;
	}
	return 0;
}*/

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