제출 #15631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15631		progressive	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	559 ms	109580 KiB

scrivener

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];
}

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