Submission #483532

#	Time	Username	Problem	Language	Result	Execution time	Memory
483532		dannyboy20031204	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	615 ms	92996 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
char c[N];
int now = 0, idx = 0, d[N], anc[N][21], p[N];
void Init() {
	now = idx = 0;
}
void TypeLetter(char L) {
	idx++;
	d[idx] = d[now] + 1;
	anc[idx][0] = now;
	for (int i = 1; i <= 20; i++) anc[idx][i] = anc[anc[idx][i - 1]][i - 1]; 
	c[idx] = L;
	p[idx] = idx;
	now = idx;
}
void UndoCommands(int U) {
	idx++;
	p[idx] = p[idx - U - 1];
	now = p[idx]; 
}
char GetLetter(int P) {
	P++;
	int u = p[now];
	for (int i = 20; i >= 0; i--) if (d[anc[u][i]] >= P) u = anc[u][i];
	return c[u]; 
}
/*
int main(){
	Init();
	TypeLetter('a');
	TypeLetter('b') ;
	cout << GetLetter(1) << '\n';
	TypeLetter('d');
	UndoCommands(2); 
	UndoCommands(1) ;
	cout << GetLetter(2) << '\n';
	TypeLetter('e'); 
	UndoCommands(1); 
	UndoCommands(5) ;
	TypeLetter('c') ;
	cout << GetLetter(2) << '\n';
	UndoCommands(2); 
	cout << GetLetter(2) << '\n';
}
*/

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