Submission #432712

#	Time	Username	Problem	Language	Result	Execution time	Memory
432712		Mounir	Crayfish scrivener (IOI12_scrivener)	C++14	5 / 100	186 ms	76716 KiB

scrivener

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;

const int N = 1e6 + 5;

vector<int> ancetres[N];
int prof[N];
char lettre[N];

int nNoeuds = 0, noeudCur = 0;

void Init() {
	prof[0] = 0;
	nNoeuds = 1;
}

void TypeLetter(char L) {
	int pere = noeudCur;
	noeudCur = nNoeuds++;
	prof[noeudCur] = prof[pere] + 1;
	lettre[noeudCur] = L;
	ancetres[noeudCur].pb(pere);

	for (int ind = 0; ind < sz(ancetres[ancetres[noeudCur][ind]]); ++ind)
		ancetres[noeudCur].pb(ancetres[ancetres[noeudCur][ind]][ind]);
}

void UndoCommands(int U) {
	noeudCur -= U + 1;
}

char GetLetter(int P) {
	int noeud = noeudCur;
	for (int i = sz(ancetres[noeud]) - 1; i >= 0; --i){
		if (i < sz(ancetres[noeud]) && prof[ancetres[noeud][i]] > P)
			noeud = ancetres[noeud][i];
	}

	return lettre[noeud];
}

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