# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1245254 | damyan_dd | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
int s[MAXN + 5], d[MAXN + 5];
int s1[MAXN + 5];
bool used[MAXN + 5];
int n;
int ask(int l, int r, bool t) {
vector <int> ret;
for (int i = 0; i < n; i++) {
if (used[i]) ret.push_back(s[i]);
else if (i < l || r < i) ret.push_back(!t);
else ret.push_back(t);
}
for (int i = 0; i < n; i++) s1[i] = ret[i];
return tryCombination(s1);
}
void exploreCave(int _n) {
n = _n;
for (int i = 0; i < n; i++) {
int l = 0, r = n, ans = -1, t = 0;
if (ask(l, r, t) < i) t = 1;
while (l <= r) {
int m = (l + r) / 2;
if (aks(l, m, t) >= i) {
r = m - 1;
ans = m;
}
else l = m + 1;
}
s[i] = t;
d[i] = ans;
}
answer(s, d);
}