#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
void exploreCave(int N) {
// vector<int> S(N, 1), D(N);
int S[N], D[N];
for(int i=0; i<N; ++i) S[i] = 1;
int ret, f;
map<int, int> done;
vector<int> r(N);
iota(r.begin(), r.end(), 0);
while(1) {
ret = tryCombination(S);
int end = ret;
if(ret == -1) {
f=1;
break;
}
int p = end+1;
// cout << "start...\n";
f=0;
shuffle(r.begin(), r.end(), rng);
REP(ind, 0, N) {
int i = r[ind];
if(done[i]) continue;
//flip ith switch
S[i] = !S[i];
ret = tryCombination(S);
if(ret == -1) {
f=1;break;
}
if(ret < end) {
D[i] = ret;
S[i] = !S[i];
done[i] = 1;
--p;
} else if(ret == end) {
D[i] = ret;
done[i] = 1;
--p;
} else
S[i] = !S[i];
if(p == 0) break;
}
// cout << "end...\n";
if(end == N || f) break;
}
if(f)
REP(i, 0, N) {
S[i] = !S[i];
ret = tryCombination(S);
// assert(ret != -1);
D[i] = ret;
S[i] = !S[i];
}
answer(S, D);
}
