Submission #483528

#	Time	Username	Problem	Language	Result	Execution time	Memory
483528		dannyboy20031204	Crayfish scrivener (IOI12_scrivener)	C++17	53 / 100	823 ms	86680 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];
void Init() {
	now = idx = 0;
}
void TypeLetter(char L) {
	idx++;
	d[idx] = d[now] + 1;
	anc[idx][0] = now;
	int r = 0;
	while ((1 << r) < d[idx]) r++;
	for (int i = 1; i <= r; i++) anc[idx][i] = anc[anc[idx][i - 1]][i - 1]; 
	c[idx] = L;
	now = idx;
}
void UndoCommands(int U) {
	idx++;
	int p = idx - U - 1;
	d[idx] = d[p];
	anc[idx][0] = p;
	int r = 0;
	while ((1 << r) < d[idx]) r++;
	for (int i = 1; i <= r; i++) anc[idx][i] = anc[anc[idx][i - 1]][i - 1];
	now = idx; 
}
char GetLetter(int P) {
	P++;
	int u = 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: 0 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 0 / 40