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>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
int opp(int d){
if (d == 1)return 0;
return 1;
}
void exploreCave(int N) {
int arr[N];
memset(arr, -1, sizeof arr);
int ans[2][N];
FOR(i, 0, N){
int temp[N];
int j = tryCombination(temp);
int d = 0; //d is colour of i th switch
if (j <= i && j > -1){
d = 1;
}
//binary search
FOR(i, 0, N){
if (arr[i] == -1)temp[i] = d;
else temp[i] = arr[i];
}
int l = 0, r = N - 1;
while(l < r){
int m = (l + r) / 2;
FOR(k, l, m + 1){
if (arr[i] == -1)
temp[i] = opp(d);
}
j = tryCombination(temp);
if (j > i || j == -1) //passes
{
l = m + 1;
}
else{
r = m;
}
}
assert(l == r);
assert(arr[l] == -1);
arr[l] = d;
ans[l][0] = d;
ans[l][1] = i;
}
answer(ans[1], ans[0]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |