#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
os << "[";
int f = 0;
for(auto i:v) {
if(f++)os << ", ";
os << i;
}
os << "]";
return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string s) {
for(char i:s){
os << i;
}
return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
cerr << t;
if(sizeof...(v)) {
cerr << ", "; debug(v...);
}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif
vector<int> used;
vector<int> numbers;
vector<int> ans1;
vector<int> ans2;
int check = false;
int query(vector<int> t) {
int num[t.size()];
for(int i = 0;i<t.size();i++) {
num[i] = t[i];
}
int ans = tryCombination(num);
if(ans == -1)return t.size();
return ans;
}
void change(int l, int r) {
for(int i = l;i<=r;i++) {
if(used[i])continue;
numbers[i]=1^numbers[i];
}
}
void find(int k, int n, int l, int r) {
if(l == r) {
dbg(l, r, k);
used[l] = true;
ans1[l] = k;
numbers[l] = 1^numbers[l];
}
else {
int mid = (l+r)/2;
change(l, mid);
int q = query(numbers);
dbg(k, l, r, q, numbers);
change(l, mid);
if(q > k) {
find(k, n, l, mid);
}
else {
find(k, n, mid+1, r);
}
}
}
void exploreCave(int N) {
int a1[N], a2[N];
numbers = used = ans1 = ans2 = vector<int> (N, 0);
for(int i = 0;i<N;i++) {
if(query(numbers) > i) {
change(0, N-1);
}
find(i, N, 0, N-1);
}
for(int i = 0;i<N;i++) {
a1[i] = ans1[i];
a2[i] = numbers[i];
}
answer(a2, a1);
}
