Submission #850922

#	Time	Username	Problem	Language	Result	Execution time	Memory
850922		promitheas	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	451 ms	155984 KiB

scrivener

//CrayfishScrivener/IOI2012
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXNLOG 22
#define MAXN 1000500

class Node {
public:
	char letter;
	Node* parents[MAXNLOG+1];
	int level;
	Node(Node* parent, char letter = 0) {
		level = parent ? parent->level + 1 : 0;
		this->letter = letter;
		parents[0] = parent;
		for (int i = 1; i < MAXNLOG; i++) {
			if (parents[i - 1])
				parents[i] = parents[i - 1]->parents[i - 1];
			else parents[i] = nullptr;
		}
	}
	Node* GetNthParent(int n) {
		Node* tar = this;
		for (int i = MAXNLOG; i >= 0; i--) {
			int p = 1 << i;
			if (n & p)tar = tar->parents[i];
			if (!tar)return nullptr;
		}
		return tar;
	}
};

Node* NODES[MAXN];
int N = 1;

void Init() {
	NODES[0] = nullptr;
}

void TypeLetter(char L) {
	NODES[N] = new Node(NODES[N - 1], L);
	N++;
}

void UndoCommands(int U) {
	NODES[N] = NODES[N - U - 1];
	N++;
}

char GetLetter(int L) {
	int l = NODES[N - 1]->level;
	return NODES[N - 1]->GetNthParent(l-L)->letter;
}
/*
void PrintAll() {
	Node* lastNode = NODES[N - 1];
	Node* n;
	int i = 0;
	while (n = lastNode->GetNthParent(i++))
		putc(n->letter, stdout);
	putc('\n', stdout);
}
*/

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