Submission #1017740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017740		pcc	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	220 ms	69236 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

const int mxn = 1e6+10;
int par[mxn][20];
int dep[mxn];
int ptr = 0;
string val(mxn,'#');
int now;
vector<int> st;

int newnode(int fa,char c){
	ptr++;
	dep[ptr] = dep[fa]+1;
	val[ptr] = c;
	par[ptr][0] = fa;
	for(int i = 1;i<20;i++)par[ptr][i] = par[par[ptr][i-1]][i-1];
	return ptr;
}

void Init() {
	now = 0;
	ptr = 0;
	st.clear();
	dep[0] = 0;
}

void TypeLetter(char L) {
	int nxt = newnode(now,L);
	now = nxt;
	//cerr<<"ADD: "<<L<<endl;
	st.push_back(now);
	return;
}

void UndoCommands(int U) {
	//cerr<<"UNDO: "<<U<<endl;
	st.push_back(st.end()[-U-1]);
	now = st.back();
	//cerr<<"UNDO DONE!"<<endl;
}

char GetLetter(int P) {
	int tar = dep[now]-P-1;
	int tmp = now;
	for(int i = 19;i>=0;i--)if(tar&(1<<i))tmp = par[tmp][i];
	//cerr<<"GET: "<<P<<endl;
	return val[tmp];
}

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