Submission #119248

#	Time	Username	Problem	Language	Result	Execution time	Memory
119248		ioilolcom	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	624 ms	75760 KiB

scrivener

#include <vector>
using namespace std;

int node = 0;
int lastnode = 0;
//vector<pair<int,char> > g[1000010];
int dp[23][1000010];
vector<int> curnode;
char chr[1000100];
int depth[1000100];

void Init() {
	dp[0][0] = -1;
	curnode.push_back(0);
	return;
}

void TypeLetter(char L) {
	node++;
	//g[lastnode].push_back(make_pair(node,L));
	dp[0][node] = lastnode;
	for(int k=1; k<=22; k++) {
		if(dp[k-1][node] == -1)
			dp[k][node] = -1;
		else
			dp[k][node] = dp[k-1][dp[k-1][node]];
	}
	chr[node] = L;
	depth[node] = depth[lastnode] + 1;
	curnode.push_back(node);
	lastnode = node;
}

void UndoCommands(int U) {
	int tmpnode = curnode[curnode.size()-U-1];
	lastnode = tmpnode;
	curnode.push_back(lastnode);
}

char GetLetter(int P) {
	int u = lastnode;
	P++;
	for(int i=22; i>=0; i--) {
		if(depth[u]-(1<<i) >= P) {
			u = dp[i][u];
		}
	}
	return chr[u];

}

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