# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1124358 | Rainmaker2627 | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
vector<bool> vis(N, false);
vector<int> p;
int cor;
void exploreCave(int N) {
int s[N], d[N];
for (int i = 0; i < N; ++i) {
p.clear();
for (int j = 0; j < N; ++j) if (!vis[j]) p.push_back(j);
for (int j = 0; j < N-i; ++j) s[p[j]]=0;
if (tryCombination(s)==i) cor=1;
else cor=0;
for (int j = 0; j < N-i; ++j) s[p[j]]=cor^1;
int l=0, r=N-i-1;
while (l<r) {
int mid=(l+r)/2;
for (int j = l; j <= mid; ++j) s[j]=cor;
int res=tryCombination(s);
for (int j = l; j <= mid; ++j) s[j]=cor^1;
if (res==i) l=mid+1;
else r=mid;
} d[p[l]]=i; s[p[l]]=cor; vis[p[l]]=true;
} answer(s, d);
}