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 pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int TryCombination(vector<int> s){
int n = s.size();
int S[n];
for(int i = 0; i < n; i++) S[i] = s[i];
return tryCombination(S);
}
void Answer(vector<int> s, vector<int> d){
int n = s.size();
int S[n], D[n];
for(int i = 0; i < n; i++) S[i] = s[i], D[i] = d[i];
answer(S, D);
}
void exploreCave(int n){
int ls = -1;
vector<int> tbc(n);
vector<int> cur(n, 0);
vector<int> door(n, -1);
for(int i = 0; i < n; i++) tbc[i] = i;
while(tbc.size() > 0){
int a = 0, b = tbc.size(); b--;
int def = TryCombination(cur);
if(def == -1) def = n;
while(a < b){
int md = (a+b)/2;
auto _cur = cur;
for(int i = 0; i <= md; i++) _cur[tbc[i]] = !_cur[tbc[i]];
if(TryCombination(_cur) == def) a = md+1;
else b = md;
}
int x = tbc[a];
tbc.erase(tbc.begin()+a);
cur[x] = !cur[x];
int nxt = TryCombination(cur);
if(nxt == -1) nxt = n;
if(nxt > def) door[x] = def;
else door[x] = nxt, cur[x] = !cur[x];
}
Answer(cur, door);
}
Compilation message (stderr)
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:27:9: warning: unused variable 'ls' [-Wunused-variable]
27 | int ls = -1;
| ^~
# | 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... |