Submission #241597

#	Time	Username	Problem	Language	Result	Execution time	Memory
241597		johutha	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1100 ms	165012 KiB

scrivener

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int upr[1000001][21];
int upu[1000001][21];
char ch[1000001];
int len[1000001];
int cnt = 0;
int bck = 0;

void Init()
{
	cnt = 1;
	bck = 0;
	for (int i = 0; i < 21; i++)
	{
		upr[0][i] = 0;
		upu[0][i] = 0;
	}
}

void update(int id)
{
	for (int i = 1; i < 21; i++)
	{
		upu[id][i] = upu[upu[id][i - 1]][i - 1];
		upr[id][i] = upr[upr[id][i - 1]][i - 1];
	}
}

void TypeLetter(char L)
{
	ch[cnt] = L;
	len[cnt] = len[bck] + 1;
	upu[cnt][0] = bck;
	upr[cnt][0] = bck;
	update(cnt);
	bck = cnt;
	cnt++;
}

void UndoCommands(signed U)
{
	int ld = bck;
	for (int i = 0; i < 21; i++)
	{
		if (U & (1<<i))
		{
			ld = upu[ld][i];
		}
	}
	ch[cnt] = ch[ld];
	upr[cnt][0] = upr[ld][0];
	upu[cnt][0] = bck;
	len[cnt] = len[ld];
	update(cnt);
	bck = cnt;
	cnt++;
}

char GetLetter(signed P)
{
	int u = len[bck] - 1 - P;
	int c = bck;

	for (int i = 0; i < 21; i++)
	{
		if (u & (1<<i))
		{
			c = upr[c][i];
		}
	}
	return ch[c];
}

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