Submission #241596

#	Time	Username	Problem	Language	Result	Execution time	Memory
241596		johutha	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1067 ms	262148 KiB

scrivener

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

using namespace std;

struct node;

using node_ptr = node*;

struct node
{
	int len;
	char l;
	node_ptr upread[21];
	node_ptr upundo[21];

	node()
	{
		l = '0';
		len = 0;
		for (int i = 0; i < 21; i++)
		{
			upread[i] = this;
			upundo[i] = this;
		}
	}

	node(char il, node_ptr lr, node_ptr lu) : l(il)
	{
		upread[0] = lr;
		upundo[0] = lu;
		len = lr->len + 1;

		for (int i = 1; i < 21; i++)
		{
			upread[i] = (upread[i - 1] != 0 ? upread[i - 1]->upread[i - 1] : node_ptr());
			upundo[i] = (upundo[i - 1] != 0 ? upundo[i - 1]->upundo[i - 1] : node_ptr());
		}
	}

	node_ptr getundo(int k)
	{
		node_ptr cp = this;

		for (int i = 20; i >= 0; i--)
		{
			if (k & (1ll<<i)) cp = cp->upundo[i];
			assert(cp != 0);
		}
		return cp;
	}

	node_ptr getread(int k)
	{
		node_ptr cp = this;

		for (int i = 20; i >= 0; i--)
		{
			if (k & (1ll<<i)) cp = cp->upread[i];
			assert(cp != 0);
		}
		return cp;
	}
};

node_ptr back;

void Init()
{
	back = new node();
}

void TypeLetter(char L)
{
	back = new node(L, back, back);
}

void UndoCommands(signed U)
{
	node_ptr rep = back->getundo(U);
	back = new node(rep->l, rep->upread[0], back);
}

char GetLetter(signed P)
{
	int ind = back->len - 1 - P;
	node_ptr rd = back->getread(ind);
	return rd->l;
}

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