Submission #135209

#	Time	Username	Problem	Language	Result	Execution time	Memory
135209		faremy	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	4 ms	632 KiB

messy

#include <vector>
#include <algorithm>
#include <string>

#include "messy.h"


void toogle(char &c)
{
	if (c == '0')
		c = '1';
	else
		c = '0';
}

std::vector<int> concatenate(std::vector<int> a, std::vector<int> b)
{
	std::vector<int> c = a;
	for (int i : b)
		c.emplace_back(i);
	return c;
}

std::vector<int> invert(std::vector<int> a)
{
	std::vector<int> b = a;
	for (int i = 0; i < (int)a.size(); i++)
		b[a[i]] = i;
	return b;
}

void createset(int left, int right, std::string base, int length)
{
	if (right - left == 1)
		return;

	for (int iBit = left; iBit < (left + right) / 2; iBit++)
	{
		toogle(base[iBit]);
		add_element(base);
		toogle(base[iBit]);
	}

	std::string nextBase(length, '0');
	for (int iBit = left; iBit < right; iBit++)
		toogle(nextBase[iBit]);
	
	createset(left, (left + right) / 2, nextBase, length);
	createset((left + right) / 2, right, nextBase, length);
}

std::vector<int> findperm(std::vector<int> positions, std::string base, int length)
{
	if (positions.size() == 1)
		return positions;

	std::vector<int> leftPositions, rightPositions;
	for (int bit : positions)
	{
		toogle(base[bit]);
		if (check_element(base))
			leftPositions.emplace_back(bit);
		else
			rightPositions.emplace_back(bit);
		toogle(base[bit]);
	}

	std::string nextBase(length, '0');
	for (int bit : positions)
		toogle(nextBase[bit]);
	return concatenate(findperm(leftPositions, nextBase, length), findperm(rightPositions, nextBase, length));
}

std::vector<int> restore_permutation(int n, int w, int r)
{
	createset(0, n, std::string(n, '0'), n);
	compile_set();

	std::vector<int> allPositions;
	for (int iPos = 0; iPos < n; iPos++)
		allPositions.emplace_back(iPos);
	return invert(findperm(allPositions, std::string(n, '0'), n));
}

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