Submission #285261

#	Time	Username	Problem	Language	Result	Execution time	Memory
285261		TMJN	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	628 ms	94456 KiB

scrivener

int dp[1000000][21];
int len[1000000];
char c[1000000];
int t[1000000];
int cnt;

void Init() {
	len[0]=-1;
}

void TypeLetter(char L) {
	cnt++;
	len[cnt]=len[cnt-1]+1;
	t[cnt]=cnt;
	c[cnt]=L;
	dp[cnt][0]=t[cnt-1];
	for(int i=0;i<=19;i++){
		dp[cnt][i+1]=dp[dp[cnt][i]][i];
	}
}

void UndoCommands(int U) {
	cnt++;
	len[cnt]=len[cnt-U-1];
	t[cnt]=t[cnt-U-1];
	for(int i=0;i<19;i++){
		dp[cnt][i+1]=dp[dp[cnt][i]][i];
	}
}

char GetLetter(int P) {
	int p=t[cnt];
	int l=len[p];
	for(int i=20;i>=0;i--){
		if(l-(1<<i)>=P){
			l-=(1<<i);
			p=dp[p][i];
		}
	}
	return c[p];
}

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