Submission #1220612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220612		boclobanchat	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	307 ms	94312 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+69;
int it[MAXN],dis[MAXN],child[MAXN][22],cnt=0;
char c[MAXN];
void Init() {}
void TypeLetter(char L)
{
	cnt++,c[cnt]=L,dis[cnt]=dis[it[cnt-1]]+1,child[cnt][0]=it[cnt-1],it[cnt]=cnt;
	for(int i=1;i<=20;i++) child[cnt][i]=child[child[cnt][i-1]][i-1];
}
void UndoCommands(int U)
{
	it[cnt+1]=it[cnt-U],cnt++;
}
char GetLetter(int P)
{
	int k=dis[it[cnt]]-P-1,pos=it[cnt];
	for(int i=20;i+1;i--) if(k&(1<<i)) pos=child[pos][i];
	return c[pos];
}

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