Submission #432750

#	Time	Username	Problem	Language	Result	Execution time	Memory
432750		Mounir	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	867 ms	91532 KiB

scrivener

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
 
const int N = 1e6 + 5, B = 20;
 
int ancetres[N][B];
int prof[N];
char lettre[N];
int noeudInst[N];
 
int nNoeuds = 0, noeudCur = 0;
 
void dbg(){
	/*vector<int> parcours;
	int noeud = noeudCur;
	while (noeud > 0){
		parcours.pb(noeud);
		noeud = ancetres[noeud][0];
	}
 
	reverse(parcours.begin(), parcours.end());
	cout << "DBG\n";
	for (int e : parcours)
		cout << lettre[e];
	cout << endl;
	for (int e : parcours)
		cout << prof[e] << " ";
	cout << endl << endl;*/
}
 
void Init() {
	prof[0] = 0;
	noeudInst[0] = 0;
	nNoeuds = 1;

	for (int noeud = 0; noeud < N; ++noeud)
		for (int ind = 0; ind < B; ++ind)
			ancetres[noeud][ind] = -1;
}
 
void TypeLetter(char L) {
	int pere = noeudCur;
	noeudInst[nNoeuds] = nNoeuds;
	noeudCur = nNoeuds++;
	prof[noeudCur] = prof[pere] + 1;
	lettre[noeudCur] = L;

	int mid = pere, ind;
	for (ind = 0; ind < B && ancetres[mid][ind] != -1; ++ind){
		ancetres[noeudCur][ind] = mid;
		mid = ancetres[mid][ind];
	}
	ancetres[noeudCur][ind] = mid;
 
//	dbg();
}
 
void UndoCommands(int U) {
	noeudCur = noeudInst[nNoeuds - 1 - U];
	noeudInst[nNoeuds++] = noeudCur;
	//dbg();
}
 
char GetLetter(int P) {
	int noeud = noeudCur;
	for (int i = B - 1; i >= 0; --i){
		if (ancetres[noeud][i] != -1 && prof[ancetres[noeud][i]] > P)
			noeud = ancetres[noeud][i];
	}
 
	return lettre[noeud];
}

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