Submission #147318

#	Time	Username	Problem	Language	Result	Execution time	Memory
147318		Diuven	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	749 ms	93524 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<=20; 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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40