Submission #341454

#	Time	Username	Problem	Language	Result	Execution time	Memory
341454		Kerim	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	604 ms	137964 KiB

scrivener

#define MAXN 1000003
#include "stdio.h"
void Init() {}
const int LOGN=20;
int nd,now,P[MAXN][LOGN],tree[MAXN][26];
int where[MAXN],id,lvl[MAXN];
char arr[MAXN];
char get(int x){int tmp=now;
	for(int i=LOGN-1;i>=0;i--)
		if(x>=(1<<i))
			tmp=P[tmp][i],x-=(1<<i);
	return arr[tmp];
}	
void TypeLetter(char L) {
	if(!tree[now][L-'a']){
		tree[now][L-'a']=++nd;
		arr[nd]=L;
	}
	int to=tree[now][L-'a'];
	P[to][0]=now;lvl[to]=lvl[now]+1;now=to;
	for(int i=1;i<LOGN;i++)
		if(P[now][i-1])
			P[now][i]=P[P[now][i-1]][i-1];
	where[++id]=now;
	//printf("ADD %d\n",now);
}
void UndoCommands(int U) {
	now=where[id-U];where[++id]=now;
	//printf("UNDO %d\n",now);
}
char GetLetter(int P) {
	//printf("%d %d\n",now,lvl[now]);
	return get(lvl[now]-P-1);
}

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