Submission #94647

#	Time	Username	Problem	Language	Result	Execution time	Memory
94647		Retro3014	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	841 ms	70252 KiB

scrivener

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define MAX_N 1000000
#define MAX_LN 20
vector<char> c;
int idx[MAX_N+1];
int fr[MAX_N+1][MAX_LN+1];
int ln[MAX_N+1];
int index=0;
int t = 0;

void Init(){
	c.clear();
	ln[0] = -1;
	index = t = 0;
}

void TypeLetter(char L) {
	//cout<<index<<endl;
	fr[c.size()][0] = index;
	ln[c.size()] = ln[index]+1;
	index = c.size();
	c.push_back(L);
	for(int i=1; i<=MAX_LN; i++){
		fr[index][i] = fr[fr[index][i-1]][i-1];
	}
	idx[t++] = index;
}

void UndoCommands(int U) {
	//cout<<index<<endl;
	index = idx[t-U-1];
	idx[t++] = index;
}

char GetLetter(int P) {
	//cout<<index<<endl;
	int now = index;
	P = ln[now] - P;
	int k = (1<<20);
	for(int i=20; i>=0; i--){
		if(k<=P){
			P-=k;
			now = fr[now][i];
		}
		k = (k>>1);
	}
	//cout<<"*"<<now<<endl;
	return c[now];
}

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