#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=5005;
int state[MAXN],saklar[MAXN],benar,it; //saklar ke i 0/1, door ke i saklarnya yang mana
bool sudah[MAXN];
vector<int> belom;
bool valid(){
int ret=tryCombination(state);
return ret>it || ret==-1;
}
void DNC(int ki,int ka){
if(ki==ka){
saklar[it]=ki;
state[ki]=benar;
sudah[ki]=true;
}
int mid=(ki+ka)/2;
for(int i=ki;i<=mid;i++)state[belom[i]]=1-benar;
if(valid()){
for(int i=ki;i<=mid;i++)state[belom[i]]=benar;
DNC(mid+1,ka);
}
else{
for(int i=ki;i<=mid;i++)state[belom[i]]=benar;
DNC(ki,mid);
}
}
void exploreCave(int N) {
for(it=0;it<N;it++){
//try door i
belom.clear();
for(int j=0;j<N;j++){
if(!sudah[j])belom.push_back(j);
}
for(auto isi : belom)state[isi]=0;
if(valid())benar=0;
else{
benar=1;
for(auto isi : belom)state[isi]=1;
}
DNC(0,belom.size()-1);
}
answer(state,saklar);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
512 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
too much calls on tryCombination() |
2 |
Halted |
0 ms |
0 KB |
- |