Submission #285259

#	Time	Username	Problem	Language	Result	Execution time	Memory
285259		TMJN	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	516 ms	69240 KiB

scrivener

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

void Init() {
	
}

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) {
	P++;
	int p=t[cnt];
	int l=len[p];
	for(int i=20;i>=0;i--){
		if(l-(1<<i)>=P){
			p=dp[p][i];
		}
	}
	return c[p];
}

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