/*
Brute force w/ random to eliminate worse case scenarios
*/
//#include "grader.h"
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
void exploreCave(int N) {
srand (time(NULL));
int S[N], D[N];
bool done[N], dd1[N];
ffi S[i] = 0, done[i] = dd1[i] = false;
int farprev = tryCombination(S);
if (farprev == -1) farprev = N+1;
int diff = 0;
S[0] = 1;
dd1[0] = true;
int far = tryCombination(S);
if (far == -1) far = N+1;
bool good = false;
while (!good) {
//w << diff c far s farprev<<e;
/// React to the difference
if (far < farprev) {S[diff] = 1-S[diff]; done[diff] = true; D[diff] = far; ffi dd1[i] = false;}
else if (far > farprev) {done[diff] = true; D[diff] = farprev; ffi dd1[i] = false;}
//ffi w<< done[i]<< " "; w<<e;
//ffi w<< dd1[i] << " "; w<<e;
good = true;
ffi if (!done[i]) good = false;
if (good) break;
while (dd1[diff] || done[diff]) {
diff += rand();
diff %= N;
//w<< diff<<e;
}
dd1[diff] = true;
S[diff] = 1-S[diff];
farprev = far;
far = tryCombination(S);
if (far == -1) far = N+1;
}
//w<< "DADASD"<<e;
answer(S, D);
}
