Submission #535861

#	Time	Username	Problem	Language	Result	Execution time	Memory
535861		cig32	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	834 ms	86636 KiB

scrivener

#include<iostream>
using namespace std;
const int LIM=1e6+7, LG=20;
int ile[LIM], nxt[LIM][LG], sum[LIM][LG], akt;
char V[LIM];
void licz() {
	for(int i=1; i<LG; ++i) {
		nxt[akt][i]=nxt[nxt[akt][i-1]][i-1];
	}
}
void Init() {}
void TypeLetter(char x) {
	++akt;
	V[akt]=x;
	ile[akt]=ile[akt-1]+1;
	if(V[akt-1]=='0') nxt[akt][0]=nxt[akt-1][0];
	else nxt[akt][0]=akt-1;
	licz();
}
void UndoCommands(int x) {
	++akt;
	V[akt]='0';
	ile[akt]=ile[akt-x-1];
	if(V[akt-x-1]=='0') nxt[akt][0]=nxt[akt-x-1][0];
	else nxt[akt][0]=akt-x-1;
	licz();
}
char GetLetter(int x) {
	x=ile[akt]-x;
	if(V[akt]!='0') --x;
	int p=akt;
	for(int i=0; i<LG; ++i) if(x&(1<<i)) p=nxt[p][i];
	return V[p];
}

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