Submission #131873

#	Time	Username	Problem	Language	Result	Execution time	Memory
131873		arthurconmy	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	733 ms	86792 KiB

scrivener

/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;

#define REP(i,a,b) \
for(int i=(a); i<=(b); i++)

#define REPb(i,a,b) \
for(int i=(a); i>=(b); i--)

int p2[20];
int parent[20][1000001];
char letter_pres[1000001];
int cur_len[1000001];
int cur=0;

// vector<int> history;

void Init()
{
	REP(i,0,19)
	{
		parent[0][i]=-1;
	}

	p2[0]=1;

	REP(i,1,19)
	{
		p2[i]=p2[i-1]+p2[i-1];
	}
}

void TypeLetter(char L)
{
	parent[0][cur+1]=cur;
	cur++;

	letter_pres[cur]=L;

	cur_len[cur]=cur_len[cur-1]+1;

	REP(i,1,19)
	{
		parent[i][cur] = parent[i-1][parent[i-1][cur]];
	}
}

void UndoCommands(int U)
{
	int v_copying = cur - U;
	cur++;

	REP(i,0,19)
	{
		parent[i][cur] = parent[i][v_copying];
	}

	letter_pres[cur]=letter_pres[v_copying]; // could get iffy - unitialised char ???
	cur_len[cur]=cur_len[v_copying];
}

char GetLetter(int P) 
{
	int length = cur_len[cur];
	P++; // not zero-indexed anymore

	int v=cur;

	int up_trav = length-P;

	REPb(i,19,0)
	{
		if(up_trav >= p2[i])
		{
			v=parent[i][v];
			up_trav-=p2[i];
		}
	}

	#ifdef ARTHUR_LOCAL
		cout << letter_pres[v] << endl;
	#endif

	return letter_pres[v];
}


// int main()
// {
// 	#ifdef ARTHUR_LOCAL
// 		ifstream cin("input.txt");
// 	#endif

// 	Init();
// 	TypeLetter('a');
// 	TypeLetter('b');
// 	GetLetter(1);
// 	TypeLetter('d');
// 	UndoCommands(2);
// 	UndoCommands(1);
// 	GetLetter(2);
// 	TypeLetter('e');
// 	UndoCommands(1);
// 	UndoCommands(5);
// 	TypeLetter('c');
// 	GetLetter(2);
// 	UndoCommands(2);
// 	GetLetter(2);
// }

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