#include "cave.h"
#include <iostream>
#include <cassert>
int NNN;
void listout(int list_[], int N) {
for (int i = 0;i < N;i++) {
std::cout << list_[i] << " ";
}
std::cout << "\n";
}
bool try_switch(int switch_number, int combination[]) {
int r = tryCombination(combination);
// listout(combination, NNN);
// std::cout << "Result is: " << r << " " << switch_number <<"\n";
if (r == switch_number) {
return true;
} else {
return false;
}
}
void prepare(int found[], int N, int base[]) {
for (int i = 0;i < N;i++) {
assert(found[i] == -1 || found[i] == 0 || found[i] == 1);
if (found[i] == 0 || found[i] == -1) {
base[i] = 0;
} else {
base[i] = 1;
}
}
}
void swap(int found[], int l, int r, int base[]) {
for (int i = l;i <= r;i++) {
if (found[i] == -1) {
base[i] = !base[i];
}
}
}
int find_matching(int found[], int current, int N) {
int base[N];
NNN = N;
prepare(found, N, base);
int l = 0;
int r = N-1;
int mid;
bool result = try_switch(current, base);
while (l < r) {
mid = l + (r - l)/2;
swap(found, l, mid, base);
// std::cout << "First: " << l << " " << r << "\n";
// listout(base, N);
bool new_result = try_switch(current, base);
swap(found, l, mid, base);
// std::cout << "Second: "<< l << " " << r << "\n";
// listout(base, N);
if (new_result != result) {
r = mid;
} else {
l = mid+1;
}
}
if (result) {
found[l] = 1;
} else {
found[l] = 0;
}
// std::cout << "\n\n\n";
return l;
}
void exploreCave(int N) {
int found[N];
int matching[N];
for (int i = 0;i < N;i++) {
found[i] = -1;
}
for (int i = 0;i < N;i++) {
int r;
matching[r = find_matching(found, i, N)] = i;
// std::cout << "a" << r << "a ";
}
answer(found, matching);
std::cout << "\n";
}
