Submission #622268

#	Time	Username	Problem	Language	Result	Execution time	Memory
622268		M_W	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	892 ms	94412 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
int idx[1000002], up[1000002][21], cnter = 0, cur = 0, lv[1000002];
char val[1000002];

void Init(){}

int get_depth(int cur){
	return int(ceil(log2(lv[cur]))) + 1;
} 

char GetLetter(int P){
	int find = lv[cur] - (P + 1); int u = cur;
	for(int i = get_depth(cur); i >= 0; i--){
		if(find >= (1 << i)){
			u = up[u][i]; find -= (1 << i);
		}
	}
	return val[idx[u]];
}

void TypeLetter(char L){
	val[++cnter] = L; idx[cnter] = cnter;
	up[cnter][0] = cur; lv[cnter] = lv[cur] + 1;
	
	cur = cnter; val[cnter] = L;
	for(int i = 1; i <= get_depth(cur); i++) up[cnter][i] = up[up[cnter][i - 1]][i - 1];
}

void UndoCommands(int U){
	cur -= U; idx[++cnter] = idx[cur];
	up[cnter][0] = up[cur][0]; lv[cnter] = lv[cur];
	
	for(int i = 1; i <= get_depth(cur); i++) up[cnter][i] = up[up[cnter][i - 1]][i - 1];
	cur = cnter;
}

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