Submission #1012117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012117		amirhoseinfar1385	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	244 ms	94544 KiB

scrivener

#include<bits/stdc++.h>
//#include "scrivener.pas"
//#include "scrivener.h"
using namespace std;
const int maxn=1000000+10,lg=20;
int par[maxn],sp[lg][maxn],vas[maxn],ted[maxn];
int now=-1;
char wtf[maxn];

void Init(){

}

void calsp(int i){
	sp[0][i]=par[i];
	for(int j=1;j<lg;j++){
		sp[j][i]=sp[j-1][sp[j-1][i]];
	}
}

void TypeLetter(char L){
	now++;
	vas[now]=1;
	wtf[now]=L;
	if(now==0){
		ted[now]=1;
		return ;
	}
	if(vas[now-1]==1){
		par[now]=now-1;
		ted[now]=ted[par[now]]+1;
		calsp(now);
		return ;
	}
	par[now]=par[now-1];
	ted[now]=ted[par[now]]+1;
	calsp(now);
}

void UndoCommands(int U){
	now++;
	vas[now]=0;
	par[now]=now-U-1;
	if(vas[par[now]]==0){
		par[now]=par[par[now]];
	}
	ted[now]=ted[par[now]];
}

char GetLetter(int P){
	P++;
	int te=ted[now];
	int fn=now;
	if(vas[now]==0){
		fn=par[now];
	}
	int x=te-P;
	for(int i=0;i<lg;i++){
		if((x>>i)&1){
			fn=sp[i][fn];
		}
	}
	return wtf[fn];
}

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