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