Submission #1091717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091717		4QT0R	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	521 ms	93520 KiB

scrivener

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

struct node{
	int prv;
	int sz;
	char tp;
	int jmp[20];
};

int t=0;
node tab[1000003];

void Init(){
	tab[0].sz=-1;
	tab[0].prv=0;
	for (int i = 0; i<20; i++)tab[0].jmp[i]=0;
}
void TypeLetter(char L){
	t++;
	tab[t].prv=t-1;
	tab[t].sz=tab[t-1].sz+1;
	tab[t].tp=L;
	tab[t].jmp[0]=t-1;
	for (int i = 1; i<20; i++)tab[t].jmp[i]=tab[tab[t].jmp[i-1]].jmp[i-1];
}
void UndoCommands(int U){
	t++;
	tab[t].prv=tab[t-U-1].prv;
	tab[t].sz=tab[t-U-1].sz;
	tab[t].tp=tab[t-U-1].tp;
	tab[t].jmp[0]=tab[t].prv;
	for (int i = 1; i<20; i++)tab[t].jmp[i]=tab[tab[t].jmp[i-1]].jmp[i-1];
}
char GetLetter(int ind){
	int cur=t;
	for (int i = 19; i>=0; i--)if (tab[tab[cur].jmp[i]].sz>=ind)cur=tab[cur].jmp[i];
	return tab[cur].tp;
}

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