Submission #16273

#	Time	Username	Problem	Language	Result	Execution time	Memory
16273		comet	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	517 ms	91896 KiB

scrivener

struct node{
	char t;
	int x,len;
}s[1000000];
int a[1000000][20],sz,cnt;
char b[1000000];
void Init() {}

void TypeLetter(char L){
	int p=0;
	if(sz)p=s[sz-1].len;
	s[sz++]={L,cnt++,p+1};
	b[cnt-1]=L;
	if(sz>1){
		a[cnt-1][0]=s[sz-2].x;
		for(int i=1;i<20;i++)a[cnt-1][i]=a[a[cnt-1][i-1]][i-1];
	}
}

void UndoCommands(int U) {
	s[sz]=s[sz-U-1];
	sz++;
}

char GetLetter(int P) {
	int x=s[sz-1].x;
	P=s[sz-1].len-P;
	for(int i=19;i>=0;i--){
		if(P>(1<<i)){
			P-=(1<<i);
			x=a[x][i];
		}
	}
	return b[x];
}

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