# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1264553 | BlockOG | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
int tryCombination(int s[]);
void answer(int s[], int d[]);
int tryComb(int s[]) {
int res = tryCombination(s);
return res == -1 ? 5000 : res;
}
int s[5000];
bool locked[5000];
int d[5000];
void exploreCave(int n) {
fo(i, 0, n) {
fo(j, 0, n) if (!locked[j]) s[j] = 1;
int check_for = tryComb(s) > i;
int l = 0, r = n;
while (l < r - 1) {
int mid = (l + r + 1) / 2;
fo(j, 0, mid) if (!locked[j]) s[j] = check_for;
fo(j, mid, n) if (!locked[j]) s[j] = 1 - check_for;
if (tryComb(s) > i) r = mid;
else l = mid;
}
s[l] = check_for;
locked[l] = true;
d[l] = i;
}
answer(s, d);
}