Submission #394123

#	Time	Username	Problem	Language	Result	Execution time	Memory
394123		Mounir	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	484 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;

int nBits;

void ajouterElements(int gauche, int droite){
	if (gauche == droite)
		return;

	int milieu = (gauche + droite)/2;
	for (int a0 = gauche; a0 <= milieu; ++a0){
		string chaine = "";
		for (int _ = 0; _ < nBits; ++_)
			chaine += '0';
		for (int ind = gauche; ind <= droite; ++ind)
			chaine[ind] = '1';
		chaine[a0] = '0';

		//cout << "ADD " << chaine << endl;

		add_element(chaine);
	}

	ajouterElements(gauche, milieu);
	ajouterElements(milieu + 1, droite);
}

vector<int> permutation;

void retrouver(int gauche, int droite, vector<int> iChiffres){
	if (gauche == droite){
		permutation[iChiffres[0]] = gauche;
		return;
	}

	vector<int> aGauche, aDroite;
	for (int ind : iChiffres){
		string chaine = "";
		for (int _ = 0; _ < nBits; ++_)
			chaine += '0';
		for (int iChiffre : iChiffres)
			chaine[iChiffre] = '1';
		chaine[ind] = '0';

	//	cout << "ASK " << chaine << " " << check_element(chaine) << endl;

		if (check_element(chaine))
			aGauche.pb(ind);
		else
			aDroite.pb(ind);
	}
/*
	cout << "SEQ " << gauche << " " << droite << endl;
	for (int e : aGauche)
		cout << e << " ";
	cout << endl;
	for (int e : aDroite)
		cout << e << " ";
	cout << endl << endl;*/

	int milieu = (gauche + droite)/2;
	retrouver(gauche, milieu, aGauche);
	retrouver(milieu + 1, droite, aDroite);
}

vector<int> restore_permutation(int n, int w, int r) {
	nBits = n;
	permutation.resize(nBits);
	for (int ind = 0; ind < nBits; ++ind)
		permutation[ind] = ind;
	ajouterElements(0, nBits - 1);
	compile_set();
	retrouver(0, nBits - 1, permutation);
	/*for (int e : permutation)
		cout << e << " ";
	cout << endl;*/
	return permutation;
}

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30