Submission #751982

#	Time	Username	Problem	Language	Result	Execution time	Memory
751982		minhcool	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	790 ms	88628 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
 
int jump[(int)1e6+2][21];
char ch[(int)1e6+2];
int op = 0;
int dist[(int)1e6+2];
 
void Init(){
	for (int i=0; i<21; i++) jump[0][i] = 0;
	dist[0] = 0;
}
 
void TypeLetter(char L){
	op++;
	ch[op] = L;
	jump[op][0] = op-1;
	dist[op] = dist[op-1] + 1;
	for (int i=1; i<21; i++){
		jump[op][i] = jump[jump[op][i-1]][i-1];
	}
}
 
void UndoCommands(int U){
	op++;
	ch[op] = ch[op-U-1];
	jump[op][0] = jump[op-U-1][0];
	dist[op] = dist[op-U-1];
	for (int i=1; i<21; i++){
		jump[op][i] = jump[jump[op][i-1]][i-1];
	}
}
 
char GetLetter(int P){
	int d = dist[op] - P -1; 
	if (!d) return ch[op];
	int s = op;
	for (int i=0; i<21; i++){
		if (d & (1<<i)) s = jump[s][i];
	}
	return ch[s];
}

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