# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
59272 | muradeyn | Cave (IOI13_cave) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "cave.h"
#include <bits/stdc++.h>
#define SIZE 5001
using namespace std;
int connect[SIZE];
bool fxd[SIZE];
int comb[SIZE];
void b_search(int i,int l,int r) {
int curr = tryCombination(comb) , nxt;
if (curr != -1 && curr < i) curr = 0;
else curr = 1;
if (l == r) {
D[l] = i;
if (curr == 0)S[l] = 1 - comb[l];
else S[l] = comb[l];
fxd[l] = true;
return;
}
int m = (l + r) >> 1;
for (int i = l;i<=m;i++)
if (fxd[i] == false) comb[i] = 1 - comb[i];
nxt = tryCombination(comb);
if (nxt != -1 && nxt < i) nxt = 0;
else nxt = 1;
if (nxt != curr) b_search(i,l,m);
else b_search(i,m + 1,r);
}
void exploreCave()
{
for (int i = 0;i<n;i++) {
for (int j = 0;j<n;j++)
if (fxd[j] == false)comb[j] = 1;
b_search(i,0,n - 1);
}
}