Submission #434933

#	Time	Username	Problem	Language	Result	Execution time	Memory
434933		dutch	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	517 ms	67220 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

const int LIM = (int)(1e6)+1;

char val[LIM];
int u = 0, d[LIM], p[LIM][20], pos[LIM], c = 0;

void Init(){}

void TypeLetter(char l){
	val[++u] = l;
	p[u][0] = pos[c];
	d[u] = d[pos[c]] + 1;
	++c;
	pos[c] = u;
	for(int i=0; i<19; ++i) p[u][i+1] = p[p[u][i]][i];
}

void UndoCommands(int U){
	++c;
	pos[c] = pos[c-U-1];
}

char GetLetter(int P){
	int v = pos[c]; ++P;
	for(int i=0; i<20; ++i) if((d[v]-P) & (1<<i)) v = p[v][i];
	return val[v];
}

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