#include "cave.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define pr pair<int, int> #define tri array<int, 3> const int INF = 1e9 + 7; int n; void exploreCave(int N) { n = N; int pos[n], color[n], cur[n]; for (int i = 0; i < n; i++) { pos[i] = 0; color[i] = 0; cur[i] = 0; } vector<bool> found(n, 0); for (int i = 0; i < n; i++) { int c; for (int j = 0; j < n; j++) { if (!found[j]) cur[j] = 0; } int ttt = tryCombination(cur); if (ttt > i || ttt == -1) c = 0; else c = 1; color[i] = c; vector<int> idk; for (int j = 0; j < n; j++) { if (!found[j]) idk.pb(j); } int l = 0, r = idk.size(), m; while (l < r) { m = (l + r) / 2; int temp[n]; for (int j = 0; j < n; j++) { temp[j] = cur[j]; } for (int j = 0; j < l; j++) { temp[idk[j]] = (c ^ 1); } for (int j = l; j <= m; j++) { temp[idk[j]] = c; } for (int j = m+1; j < idk.size(); j++) { temp[idk[j]] = (c ^ 1); } int t = tryCombination(temp); if (t > i || t == -1) r = m; else l = m + 1; } int p = idk[l]; found[p] = 1; pos[p] = i; cur[p] = c; } answer(color, pos); }