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<iostream>
#include<set>
#include<vector>
const int maxN=5e3+1;
int n;
int S[maxN],D[maxN];
std::set<int>s;
void solve(int x){
int ans=tryCombination(S);
std::vector<int>a;
for(int k:s) a.push_back(k);
if(ans==x){
int l=0,r=(int)a.size()-1;
while(r>l){
int mid=(l+r)/2;
for(int j=0;j<=mid;j++){
S[a[j]]=1;
}
if(tryCombination(S)!=x) r=mid;
else l=mid+1;
for(int j=0;j<=mid;j++){
S[a[j]]=0;
}
}
D[a[l]]=x;
S[a[l]]=1;
s.erase(a[l]);
return;
}
int l=0,r=(int)a.size()-1;
while(r>l){
int mid=(l+r)/2;
for(int j=0;j<=mid;j++){
S[a[j]]=1;
}
if(tryCombination(S)==x) r=mid;
else l=mid+1;
for(int j=0;j<=mid;j++){
S[a[j]]=0;
}
}
D[a[l]]=x;
S[a[l]]=0;
s.erase(a[l]);
}
void exploreCave(int N) {
n=N;
for(int i=0;i<n;i++) s.insert(i),D[i]=-1,S[i]=0;
for(int i=0;i<n;i++){
solve(i);
}
answer(S,D);
}
# | 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... |