Submission #747817

#	Time	Username	Problem	Language	Result	Execution time	Memory
747817		Hacv16	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	988 ms	90432 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 2e6 + 15;
const int LOG = 22;

int dp[MAX][LOG], tam[MAX], cnt;
char letter[MAX];

void Init(){ }

void calcLift(int curNode){
	for(int j = 1; j < LOG; j++)
		dp[curNode][j] = dp[ dp[curNode][j - 1] ][j - 1];
}

void TypeLetter(char L){
	int curNode = ++cnt;
	letter[curNode] = L;

	dp[curNode][0] = cnt - 1;
	tam[curNode] = tam[cnt - 1] + 1;

	calcLift(curNode);
}
 
void UndoCommands(int U){
	int curNode = ++cnt;

	dp[curNode][0] = cnt - 1 - U;
	tam[curNode] = tam[dp[curNode][0]];

	calcLift(curNode);
}
 
char GetLetter(int P){
	int curNode = cnt; P++;

	for(int j = LOG - 1; j >= 0; j--)
		if(tam[ dp[curNode][j] ] >= P && dp[curNode][j] > 0)
			curNode = dp[curNode][j];

	return letter[curNode];
}

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