#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { int s[5000], d[5000]; for (int i = 0; i < N; i++) { s[i] = 0; d[i] = -1; } for (int i = 0; i < N; i++) { vector<int> v; for (int j = 0; j < N; j++) { if (d[j] == -1) { v.push_back(j); } } int t = tryCombination(s); int ng = -1, ok = v.size(); --ok; while (ok - ng > 1) { int mid = (ok + ng) / 2; for (int j = 0; j <= mid; j++) { s[v[j]] ^= 1; } int r = tryCombination(s); if (t == i) { if (r == i) { ng = mid; } else { ok = mid; } } else { if (r == i) { ok = mid; } else { ng = mid; } } for (int j = 0; j <= mid; j++) { s[v[j]] ^= 1; } } d[v[ok]] = i; if (t == i) { s[v[ok]] ^= 1; } } answer(s, d); }