Submission #1015567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015567		parsadox2	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	254 ms	71216 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10 , Lg = 20;

int pnt[N] , now , safar;

struct TRIE{
	struct NODE{
		int par[Lg];
		char c;
		int dis;
	} t[N];
	int pos = 1;
	void Build()
	{
		pos = 1;
		t[0].dis = -1;
		t[0].c = 'P';
	}
	void Add(int v , char c)
	{
		t[pos].par[0] = v;
		t[pos].dis = t[v].dis + 1;
		for(int i = 1 ; i < Lg ; i++)
			t[pos].par[i] = t[t[pos].par[i - 1]].par[i - 1];
		t[pos].c = c;
		pos++;
	}
	char Get(int v , int h)
	{
		int dis = t[v].dis -  h;
		for(int i = 0 ; i < Lg ; i++)  if((dis >> i) & 1)
			v = t[v].par[i];
		return t[v].c;
	}
} trie;

void Init()
{
	trie.Build();
	pnt[0] = 0;
	now = 1;
}

void TypeLetter(char c)
{
	pnt[now] = trie.pos;
	//cout << now << " : " << pnt[now] << endl;
	trie.Add(pnt[now - 1] , c);
	now++;
}

void UndoCommands(int l)
{
	pnt[now] = pnt[now - 1 - l];
	//cout << now << " : " << pnt[now] << endl;
	now++;
}

char GetLetter(int p)
{
	//cout << "ASK : " << pnt[now] << endl;
	return trie.Get(pnt[now - 1] , p);
}

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