Submission #15631

#TimeUsernameProblemLanguageResultExecution timeMemory
15631progressiveCrayfish scrivener (IOI12_scrivener)C++14
100 / 100
559 ms109580 KiB
using namespace std;
static const int MAXN=1010101;
static bool isundo[MAXN];
static int real[MAXN];
static char working[MAXN];
static int length[MAXN];
static int sparse[MAXN][25];
static int turn;
void Init()
{
	turn=1;
	real[0]=0;
	length[0]=0;
	for(int i=0;i<25;i++) sparse[0][i]=-1;
}

void TypeLetter(char L)
{
	isundo[turn]=false;
	working[turn]=L;
	length[turn]=length[turn-1]+1;
	real[turn]=turn;
	sparse[turn][0]=real[turn-1];
	for(int i=1;i<25;i++)
	{
		int v=sparse[turn][i-1];
		if(v==-1) sparse[turn][i]=-1;
		else sparse[turn][i]=sparse[v][i-1];
	}
	turn++;
	return;
}

void UndoCommands(int U)
{
	isundo[turn]=true;
	real[turn]=real[turn-U-1];
	length[turn]=length[turn-U-1];
	turn++;
	return;
}
char GetLetter(int P)
{
	int nowturn=turn-1;
	nowturn=real[nowturn];
	//printf("%d\n ",nowturn);
	int spb=length[nowturn]-P-1;
	
	int i=24;
	while(spb>0)
	{
		for(;;i--)
		{
			if(spb>=(1<<i))
			{
				spb-=1<<i;
				nowturn=sparse[nowturn][i];
				break;
			}
		}
	}
	return working[nowturn];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...