Submission #622252

#	Time	Username	Problem	Language	Result	Execution time	Memory
622252		M_W	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1076 ms	90716 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(){}

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

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 <= 20; i++) up[cnter][i] = up[up[cnter][i - 1]][i - 1];
	cur = cnter;
}

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

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