# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
713041 | lam | 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 <bits/stdc++.h>
#include "cave.h"
using namespace std;
int n;
int dau[],s[],d[];
vector <int> tmp;
void exploreCave(int N) {
/* ... */
n=N;
for (int i=0; i<n; i++) dau[i]=0;
for (int it=0; it<n; it++)
{
int temp = tryCombination(dau);
if (temp > it || temp==-1)
{
for (int i:tmp) dau[i] ^= 1;
temp = tryCombination(dau);
}
int l = 0; int r=tmp.size()-1;
while (l<r)
{
int mid=(l+r)/2;
for (int i=0; i<=mid; i++) dau[tmp[i]]^=1;
int val = tryCombination(dau);
for (int i=0; i<=mid; i++) dau[tmp[i]]^=1;
if (val>it||val==-1) r=mid;
else l=mid+1;
}
d[it] = tmp[r];
dau[d[it]] ^= 1;
for (int i=r+1; i<tmp.size(); i++) swap(tmp[i],tmp[i-1]);
tmp.pop_back();
}
answer(dau,d);
}