| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1359359 | cansu_mutlu | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int a[n];
vector<int> v;
for(int i=0;i<n;i++)
{
a[i]=0;
}
int ex = tryCombination(a);
for(int i=0;i<n;i++)
{
a[i] = 1-a[i];
int num = tryCombination(a);
if(num>=ex || num==-1)
v.push_back(i);
a[i] = 1-a[i];
}
while(ex!=-1)
{
int l = 0,r = v.size()-1;
while(l<=r)
{
int mid = (l+r)/2;
for(int i=l;i<=mid;i++) a[v[i]] = 1-a[v[i]];
int num = tryCombination(a);
for(int i=l;i<=mid;i++) a[v[i]] = 1-a[v[i]];
if(num>ex || num==-1)
{
r = mid-1;
}
else
{
l = mid+1;
}
}
a[v[l]] = 1-a[v[l]];
ex = = tryCombination(a);;
vector<int> b;
for(int i:v)
{
if(i!=l)b.push_back(i);
}
swap(b,v);
}
int b[n];
for(int i=0;i<n;i++)
{
a[i] = 1-a[i];
int num = tryCombination(a);
a[i] = 1-a[i];
b[i] = num;
}
answer(a,b);
return;
}
