Submission #590736

#	Time	Username	Problem	Language	Result	Execution time	Memory
590736		LaviniaTornaghi	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	735 ms	144708 KiB

scrivener

#include <vector>
#include <string>
#include <stdio.h>
using namespace std;

vector<vector<int>> Log;
int nd; //nodo attuale

vector<char> C;
vector<int> P;
vector<int> D;

void Ancestors()
{
	Log.push_back(vector<int>(25,0));
	Log[nd][0] = P[nd];
	
	for(int i=1; i<25; i++)
	{
		Log[nd][i] = Log[Log[nd][i-1]][i-1];		
	}
}

void Init()
{
	//crea radice
	C.push_back(' ');
	P.push_back(-1);
	D.push_back(-1);
	
	Log.push_back(vector<int>(25,0));
	
	nd = 0;
}

void UndoCommands(int U)
{
	C.push_back(C[nd-U]);
	P.push_back(P[nd-U]);
	D.push_back(D[nd-U]);
	
	Log.push_back(Log[nd-U]);
	
	nd ++;
}

void TypeLetter(char ch)
{
	C.push_back(ch);
	P.push_back(nd);
	D.push_back(D[nd]+1);
	nd ++;
	Ancestors();	
}

char GetLetter(int i)
{
	i = D[nd] - i;
	int ndattuale = nd;
	
	for(int e=0; e<25; e++)
	{
		if((1<<e) & i)//potenza di 2 contenuta
		{
			ndattuale = Log[ndattuale][e];
		}
	}
	
	return C[ndattuale];
}

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