Submission #68079

#	Time	Username	Problem	Language	Result	Execution time	Memory
68079		naderjemel	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1010 ms	212564 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int LOG = 21;
struct node
{
	char c; int s;
	node *anc[LOG];
	node(){
		for(int i=0;i<LOG;i++) anc[i] = NULL;
		s=0;
	}
}*tree [1000005];

int id;
void Init(){
	id=1;
	tree[0] = new node();

}
void TypeLetter(char L) {
	int n=id++;
	tree[n] = new node();
	tree[n]->s = tree[n-1]->s+1;
	tree[n]->c = L;
	tree[n]->anc[0]=tree[n-1];
	for(int i=1;i<LOG;i++) tree[n]->anc[i] = (tree[n]->anc[i-1]) ? (tree[n]->anc[i-1])->anc[i-1] : NULL; 
}

void UndoCommands(int U) {
	int ret=id-1-U;
	int n=id++;
	tree[n]=tree[ret];
}


char GetLetter(int P) {
	int n=id-1;
	node *h = new node();
	h=tree[n];
	int up=tree[n]->s - 1 - P;
	for(int i=LOG-1;i>=0;i--){
		if(up - (1<<i) >= 0){
			up-=(1<<i);
			h=h->anc[i];
		}
	}
	return h->c;
}

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