Submission #538811

#	Time	Username	Problem	Language	Result	Execution time	Memory
538811		new_acc	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	359 ms	53656 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-1];
	for(int i=1;i<=20;i++) jump[l][i]=jump[jump[l][i-1]][i-1];
	dep[l]=dep[zap[num-1]]+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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40