Submission #550303

#	Time	Username	Problem	Language	Result	Execution time	Memory
550303		Hanksburger	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	413 ms	86676 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
int par[1000005][20], len[1000005], n;
char c[1000005];
void Init()
{
	
}
void TypeLetter(char L)
{
	n++;
	c[n]=L;
	len[n]=len[n-1]+1;
	par[n][0]=n-1;
	for (int i=1; i<20; i++)
		par[n][i]=par[par[n][i-1]][i-1];
}
void UndoCommands(int U)
{
	n++;
	c[n]=c[n-U-1];
	len[n]=len[n-U-1];
	for (int i=0; i<20; i++)
		par[n][i]=par[n-U-1][i];
}
char GetLetter(int P)
{
	int cur=n, diff=len[n]-P-1;
	for (int i=0; i<20; i++)
		if (diff&(1<<i))
			cur=par[cur][i];
	return c[cur];
}

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