Submission #911686

#	Time	Username	Problem	Language	Result	Execution time	Memory
911686		Muhammad_Aneeq	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	533 ms	140180 KiB

scrivener

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int const N=1e6+10;
struct node
{
	char c=' ';
	int sz=0;
	node* par[22]={};
	node()
	{
		for (int i=0;i<22;i++)
			par[i]=NULL;
	}
};
vector<node*>re;
node* cur;
void Init()
{
	cur=NULL;
	re.push_back(cur);
}
void TypeLetter(char L)
{
		if (cur==NULL)
		{
			cur=new node();
			cur->c=L;
			cur->sz=1;
			re.push_back(cur);
			return;
		}
		node* z=new node();
		z->par[0]=cur;
		for (int i=1;i<22;i++)
		{
			if (z->par[i-1]==NULL)
				break;
			z->par[i]=z->par[i-1]->par[i-1];
		}
		z->c=L;
		z->sz=cur->sz+1;
		cur=z;
		re.push_back(cur);
}
void UndoCommands(int U)
{
	cur=re[re.size()-U-1];
	re.push_back(cur);
}
char GetLetter(int P)
{
	P=cur->sz-P-1;
	node* temp=cur;
	for (int i=0;i<22;i++)
	{
		if ((1<<i)&P)
			temp=temp->par[i];
	}
	return temp->c;
}

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