Submission #986348

#	Time	Username	Problem	Language	Result	Execution time	Memory
986348		Pyqe	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	806 ms	90476 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

int n=0,a[1000069],pr[1000069][20],dh[1000069];

void bd()
{
	int i;
	
	for(i=1;i<20;i++)
	{
		pr[n][i]=pr[pr[n][i-1]][i-1];
	}
}

void Init()
{
}

void TypeLetter(char ch)
{
	n++;
	a[n]=ch-'a';
	pr[n][0]=n-1;
	dh[n]=dh[n-1]+1;
	bd();
}

void UndoCommands(int x)
{
	n++;
	pr[n][0]=n-1-x;
	dh[n]=dh[n-1-x];
	bd();
}

char GetLetter(int x)
{
	int i,p=n;
	
	x++;
	for(i=19;i+1;i--)
	{
		if(dh[pr[p][i]]>=x)
		{
			p=pr[p][i];
		}
	}
	return (char)(a[p]+'a');
}

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