Submission #147314

#	Time	Username	Problem	Language	Result	Execution time	Memory
147314		Diuven	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	1077 ms	2240 KiB

scrivener

struct node{
	char c='\0';
	int up[21]={}, len=0;
} S[1000010];
int n;

void Init(){ n = 0; }

void TypeLetter(char L) {
	S[++n].c = L; S[n].len = S[n-1].len+1;
	S[n].up[0] = n-1;
	for(int i=1; i<=n; i++) S[n].up[i] = S[S[n].up[i-1]].up[i-1];
}

void UndoCommands(int U) {
	node &pv=S[n-U], &nw = S[n+1]; n++;
	nw.c = pv.c, nw.len = pv.len;
	for(int i=0; i<=20; i++) nw.up[i] = pv.up[i];
}

char GetLetter(int P) {
	int d = S[n].len-1-P, v = n;
	for(int i=20; i>=0; i--) if(d>=(1<<i))
		d-=(1<<i), v = S[v].up[i];
	return S[v].c;
}

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