Submission #469837

#	Time	Username	Problem	Language	Result	Execution time	Memory
469837		wind_reaper	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	519 ms	67268 KiB

scrivener

const int MXN = 1000001;

char s[MXN];
int up[20][MXN], D[MXN], p[MXN];
int idx = 0, c = 0;

void Init(){}

void TypeLetter(char L){
	s[++idx] = L;
	up[0][idx] = p[c];
	D[idx] = D[p[c]] + 1;
	p[++c] = idx;
	for(int i = 1; i < 20; i++) up[i][idx] = up[i-1][up[i-1][idx]];
}

void UndoCommands(int U){
	++c;
	p[c] = p[c-U-1];
}

char GetLetter(int P){
	int v = p[c]; 
	++P;
	for(int i = 19; i >= 0; --i) if((D[v] - P) & (1 << i)) v = up[i][v];
	return s[v];
}

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