#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int n, w, r;
string orig;
string inv(string a) {
for(auto &x : a) {
if(x == '0') x = '1';
else x = '0';
}
return a;
}
int lg(int n) {
if(n == 1) return 0;
return lg(n / 2) + 1;
}
string toBits(int a) {
a++;
string ret = "";
for(int i = 0; i < 3; i++) {
if((1 << i) & a) ret.push_back('1');
else ret.push_back('0');
}
return ret;
}
string f(int bitas, int ind, vector<int> vec) {
string sitas = orig;
string bts = toBits(bitas);
for(int i = 0; i < 3; i++) {
sitas[vec[i]] = bts[i];
}
sitas[ind] = '1';
return sitas;
}
vector<int> find3(){
vector<int> ret;
string last = orig;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < n; j++) {
if(last[j] == '1') continue;
last[j] = '1';
if(check_element(inv(last))) {
// cout << i << "-asis eina i " << j << "-aja pozicija, nes " << inv(last) << " egzistuoja" << endl;
ret.push_back(j);
break;
}
last[j] = '0';
}
}
return ret;
}
vector<int> restore_permutation(int N, int W, int R) {
/* add_element("0");
compile_set();
check_element("0");
*/
// cout << "vcia" << endl;
n = N; w = W; r = R;
orig = "";
int lg2 = lg(n);
for(int i = 0; i < n; i++) orig.push_back('0');
for(int i = 0; i < 3; i++) {
string sitas = orig;
for(int j = 0; j <= i; j++) {
sitas[j] = '1';
}
sitas = inv(sitas);
// cout << "Idedu " << sitas << endl;
add_element(sitas);
}
for(int i = 0; i < lg2; i++){
// cout << "ziuriu i " << i << "-aji bita:" << endl;
for(int j = 3; j < n; j++) {
if((1 << i) & j) {
string toAdd = f(i, j, {0, 1, 2});
// cout << "Idedu " << toAdd << endl;
add_element(toAdd);
}
}
}
// cout << "kompiliuojame!" << endl;
compile_set();
vector<int> pirmiTrys = find3();
for(int i = 0; i < 3; i++) {
// cout << i << "-etas tampa " << pirmiTrys[i] << endl;
}
vector<int> visi = pirmiTrys;
visi.resize(n);
for(int i = 0; i < n; i++) {
int sk = 0;
if(i == pirmiTrys[0] || i == pirmiTrys[1] || i == pirmiTrys[2]) continue;
//cout << "ziuriu, kuriuos bitus turi skaicius " << i << endl;
for(int j = 0; j < lg2; j++) {
string sitas = f(j, i, pirmiTrys);
if(check_element(sitas)) {
// cout << j << " bita turi, nes yra " << sitas << endl;
sk += (1 << j);
}else {
// cout << j << " bito neturi, nes nera " << sitas << endl;
}
}
// cout << sk << "-etas tampa " << i << endl;
visi[sk] = i;
}
vector<int> ans(n);
for(int i = 0; i < n; i++) {
ans[visi[i]] = i;
}
return ans;
}
/*
8 100 100
7 4 5 3 1 0 2 6
*/
