#include "cave.h"
#define MAX 5123
int ans[MAX];
int att[MAX];
int crsp[MAX];
void invert(int l, int r) {
//printf("inverting %d to %d\n", l, r);
for (int i = l; i <= r; i++)
att[i] = !att[i];
}
int goFor(int N) {
for (int j = 0; j < N; j++) {
if (ans[j] != -1) att[j] = ans[j];
}
/*printf("trying:\n");
for (int i = 0; i < N; i++) {
printf("%d ", att[i]);
}
printf("\n");*/
int ret = tryCombination(att);
//printf("got %d\n", ret);
return ret;
}
void exploreCave(int N) {
for (int i = 0; i < N; i++) {
ans[i] = -1;
att[i] = 0;
}
for (int i = 0; i < N; i++) {
int ret = goFor(N);
int lastState = ret == i;
int l = 0, r = N - 1;
while (l != r) {
int mid = (l + r) / 2;
invert(l, mid);
ret = goFor(N);
int state = ret == i;
if (state == lastState) {
l = mid + 1;
}
else {
r = mid;
}
lastState = state;
}
crsp[l] = i;
//printf("lastState is %d\n", lastState);
if (lastState)
ans[l] = !att[l];
else
ans[l] = att[l];
//printf("ans[%d]=%d\n", l, ans[l]);
//printf("crsp[%d]=%d\n\n", l, crsp[l]);
}
answer(ans, crsp);
}
