Submission #706682

#	Time	Username	Problem	Language	Result	Execution time	Memory
706682		starplat	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	700 ms	97420 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
void Init();
void TypeLetter(char L);
void UndoCommands(int U);
char GetLetter(int P);
int pnt,cmd[1000005],dp[1000005];
int lift[25][1000005],ans[1000005];
void Init(){
	pnt=0;
	for (int i=0;i<=1000000;i++) cmd[i]=i;
}
void TypeLetter(char L){
	int par=cmd[pnt];
	ans[++pnt]=L;
	lift[0][pnt]=par;
	for (int i=1;i<=20;i++){
		lift[i][pnt]=lift[i-1][lift[i-1][pnt]];
	}
	dp[pnt]=dp[par]+1;
}
void UndoCommands(int U){
	++pnt;
	cmd[pnt]=cmd[pnt-U-1];
}
char GetLetter(int P){
	int x=cmd[pnt];
	for (int i=20;i>=0;i--){
		if (dp[lift[i][x]]>=P+1){
			x=lift[i][x];
		}
	}
	return ans[x];
}
/*int main(){
	Init();
	while (true){
		char type,c; cin>>type>>c;
		if (type=='A') TypeLetter(c);
		else if (type=='B') UndoCommands(c-'0');
		else cout<<GetLetter(c-'0')<<"\n";
	}
}*/

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