#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; st[i] = 0; } for(int i = 0;i < N; i++) { int x = tryCombination(st); int l = 0, r = N - 1, jog = 0; while(l <= r) { int mid = (l + r) / 2; for(int j = 0; j < N; j++) { if(vis[j]) { a[j] = st[j]; } else { if(j >= l && j <= mid) a[j] = 1; else a[j] = 0; } } int y = tryCombination(a); 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; } } st[jog] = (x!=i) - a[jog]; dr[jog] = i; vis[jog] = 1; } answer(st, dr); }