제출 #1015567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015567		parsadox2	크레이피쉬 글쓰는 기계 (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