Submission #822067

#	Time	Username	Problem	Language	Result	Execution time	Memory
822067		PenguinsAreCute	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	293 ms	17592 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for(int i = a; i < b; i++)
int par[1000069], kpar[1000069], h[1000069], cnt; char c[1000069];
void Init() {}
void TypeLetter(char L) {
	cnt++;
	par[cnt]=cnt-1;
	c[cnt]=L;
	h[cnt]=h[cnt-1]+1;
	if(h[cnt-1]+h[kpar[kpar[cnt-1]]]==(h[kpar[cnt-1]]<<1)) kpar[cnt]=kpar[kpar[cnt-1]];
	else kpar[cnt]=cnt-1;
}
void UndoCommands(int U) {
	cnt++;
	par[cnt]=par[cnt-U-1];
	kpar[cnt]=kpar[cnt-U-1];
	h[cnt]=h[cnt-U-1];
	c[cnt]=c[cnt-U-1];
}
char GetLetter(int P) {
	int cur=cnt;
	while(h[cur]>P+1) {
		if(kpar[cur]!=-1&&h[kpar[cur]]>=P+1) cur=kpar[cur];
		else cur=par[cur];
	}
	return c[cur];
}

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