Submission #131816

#	Time	Username	Problem	Language	Result	Execution time	Memory
131816		hugo_pm	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	4 ms	640 KiB

messy

#include <vector>
#include "messy.h"
using namespace std;

int nbBits;
vector<int> permAns;

string vide;

void preparer(int gauche, int droite)
{
	if (gauche == droite) return;
	string rq = vide;
	for (int pos = 0; pos < nbBits; ++pos) {
		rq[pos] = ((gauche <= pos && pos <= droite) ? '0' : '1');
	}

	int mid = (gauche + droite) / 2;

	for (int pos = gauche; pos <= mid; ++pos) {
		rq[pos] = '1';
		fflush(stdout);
		add_element(rq);
		rq[pos] = '0';
	}

	preparer(gauche, mid);
	preparer(mid+1, droite);
}

void catchMe(int gaucheBase, int droiteBase, vector<bool> estInclus)
{
	if (gaucheBase == droiteBase) {
		for (int pos = 0; pos < nbBits; ++pos) {
			if (estInclus[pos]) {
				permAns[pos] = gaucheBase;
			}
		}
		return;
	}

	string rq = vide;

	vector<bool> incLeft(nbBits, false);
	vector<bool> incRight(nbBits, false);

	for (int pos = 0; pos < nbBits; ++pos) {
		rq[pos] = (estInclus[pos] ? '0' : '1');
	}

	for (int pos = 0; pos < nbBits; ++pos) {
		if (estInclus[pos]) {
			rq[pos] = '1';
			bool dansSet = check_element(rq);
			rq[pos] = '0';
			if (dansSet) incLeft[pos] = true;
			else incRight[pos] = true;
		}
	}

	int mid = (gaucheBase+droiteBase) / 2;
	catchMe(gaucheBase, mid, incLeft);
	catchMe(mid+1, droiteBase, incRight);
}

std::vector<int> restore_permutation(int _n, int _w, int _r)
{
	nbBits = _n;
	vide.resize(nbBits);
	permAns.resize(nbBits);
	preparer(0, nbBits-1);
	compile_set();

	catchMe(0, nbBits-1, vector<bool>(nbBits, true));
	return permAns;
}

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