Submission #446862

#	Time	Username	Problem	Language	Result	Execution time	Memory
446862		ComPhyPark	Crayfish scrivener (IOI12_scrivener)	C++14	74 / 100	680 ms	262148 KiB

scrivener

#include<cstdio>
#include<malloc.h>
#include<vector>
using namespace std;
typedef struct node {
	int depth;
	char data;
	node* anc[22];
	node* child[26];
	void init(char d, node* par) {
		data = d;
		if (par != NULL) {
			depth = par->depth + 1;
		}
		else depth = 0;
		int i = 0;
		anc[0] = par;
		while (anc[i] != NULL) {
			i++;
			anc[i] = anc[i - 1]->anc[i - 1];
		}
		for (; i < 22; i++)anc[i] = NULL;
		for (int i = 0; i < 26; i++)child[i] = NULL;
	}
	node* getChild(char nxt) {
		if (child[nxt - 'a'] == NULL) {
			child[nxt - 'a'] = (node*)malloc(sizeof(node));
			child[nxt - 'a']->init(nxt, this);
		}
		return child[nxt - 'a'];
	}
	char getAnc(int d) {
		if (!d)return data;
		int i = 0;
		while (!(d & 1)) {
			d >>= 1;
			i++;
		}
		return anc[i]->getAnc((d ^ 1) << i);
	}
}node;
vector<node*>v;
void Init() {
	node* nd = (node*)malloc(sizeof(node));
	nd->init(0, NULL);
	v.push_back(nd);
}
void TypeLetter(char a) {
	v.push_back(v.back()->getChild(a));
}
void UndoCommands(int a) {
	v.push_back(v[v.size() - a - 1]);
}
char GetLetter(int a) {
	return v.back()->getAnc(v.back()->depth - a - 1);
}

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