Submission #538812

#	Time	Username	Problem	Language	Result	Execution time	Memory
538812		new_acc	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	629 ms	65532 KiB

scrivener

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10; 
int zap[N],jump[N][21],dep[N];
char zn[N];
int l=1,num;
void Init(){
	zap[0]=1;
	for(int i=0;i<=20;i++) jump[1][i]=1;
}
void TypeLetter(char a){
	jump[++l][0]=zap[num];
	for(int i=1;i<=20;i++) jump[l][i]=jump[jump[l][i-1]][i-1];
	dep[l]=dep[zap[num]]+1;
	zn[l]=a,zap[++num]=l;
}
void UndoCommands(int x){
	num++;
	zap[num]=zap[num-x-1];
}
char GetLetter(int p){
	p++;
	int a=zap[num];
	for(int i=20;i>=0;i--)
		if(dep[jump[a][i]]>=p) a=jump[a][i];
	return zn[a];
}

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