# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
256543 | Harry464 | 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 <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include "cave.h"
typedef int ll;
using namespace std;
void exploreCave(int n)
{
ll sw[n];
ll odg[n];
for (int i = 0; i < n; i++)
sw[i] = 0, odg[i] = -1;
for (int j = 0; j < n; j++){
for (int i = 0; i < n; i++)
t[i] = sw[i];
vector <ll> free;
for (int i = 0; i < n; i++)
if (odg[i] == -1)
free.push_back(i), sw[i] = 1;
ll ask = tryCombination(t);
ll trig;
if (ask == j)
trig = 0;
else
trig = 1;
ll l = 0, r = free.size() - 1;
while (l < r){
ll mid = (l+r)/2;
for (int i = l; i <= mid; i++)
t[free[i]] = trig;
for (int i = 0; i < l; i++)
t[free[i]] = (trig+1)%2;
for (int i = mid + 1; i < free.size(); i++)
t[free[i]] = (trig+1)%2;
ask = tryCombination(t);
if (ask == j)
l = mid + 1;
else
r = mid;
}
sw[l] = trig;
odg[l] = j;
}
answer(sw,odg);
}