# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
474237 | MB2 | 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 ll long long
using namespace std;
ll S[5009],D[5009];
bool fix[5009];
void swp(ll x, ll y)
{
for(ll i=x; i<=y; i++)
{
if(!fix[i])
S[i]^=1;
}
}
ll search(ll cur, ll n)
{
ll r=n-1,l=0;
if(tryCombination(S)!=cur)
swp(0,n-1);
while(r!=l)
{
ll mid=(l+r)/2;
swp(l,mid);
ll inf=tryCombination(S);
swp(l,mid);
if(inf==cur)
l=mid+1;
else
r=mid;
}
return r;
}
void exploreCave(ll x)
{
for(ll i=0; i<x; i++)
{
ll cur=search(i,x);
fix[cur]=true;
S[cur]^=1;
D[cur]=1;
}
answer(S,D);
}