Submission #400627

#	Time	Username	Problem	Language	Result	Execution time	Memory
400627		Jasiekstrz	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	497 ms	98244 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int N=1e6,LG=20;
int it;
char tab[N+10];
int rt[N+10];
int jmp[N+10][LG+2];
int siz[N+10];
void Init()
{
	it=0;
	return;
}
void TypeLetter(char L)
{
	it++;
	tab[it]=L;
	rt[it]=it;
	siz[it]=siz[it-1]+1;
	jmp[it][0]=rt[it-1];
	for(int i=1;i<=LG;i++)
		jmp[it][i]=jmp[jmp[it][i-1]][i-1];
	return;
}
void UndoCommands(int U)
{
	it++;
	rt[it]=rt[it-U-1];
	siz[it]=siz[it-U-1];
	return;
}
char GetLetter(int P)
{
	P=siz[it]-P-1;
	int x=rt[it];
	for(int i=0;i<=LG;i++)
	{
		if(P%2==1)
			x=jmp[x][i];
		P/=2;
	}
	return tab[x];
}

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