#include "bits/stdc++.h" // #include "grader.c" #include "cave.h" #define MAXN 500005 int dr[MAXN], vis[MAXN], st[MAXN], a[MAXN]; void exploreCave(int N) { for(int i = 0; i < N; i++) { dr[i] = i; a[i] = 0; } for(int i = 0;i < N; i++) { int l = 0, r = N - 1, jog = -1; int x = tryCombination(a); while(l <= r) { int mid = (l + r) / 2; for(int j = 0; j < N; j++) { if(vis[j]) { st[j] = a[j]; } else { if(j >= l && j <= mid) st[j] = 1; else st[j] = 0; } } int y = tryCombination(st); bool tr = 0; if(x == i) { if(y != i) { tr = 1; } } else { if(y == i) { tr = 1; } } if(tr) { r = mid - 1; jog = mid; } else { l = mid + 1; } } a[jog] = (x == i); dr[jog] = i; vis[jog] = 1; } answer(a, dr); }