#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));
}
