#include "insects.h"
#include <vector>
using namespace std;
int nbInside = 0;
vector<bool> in, alive;
void inside(int i) {
if(in[i]) return;
in[i] = true;
move_inside(i);
nbInside++;
}
void outside(int i) {
if(!in[i]) return;
in[i] = false;
move_outside(i);
nbInside--;
}
int getNbType(int N) {
int nb = 0;
for(int i = 0; i < N; i++)
if(alive[i]) {
nb++;
inside(i);
in[i] = true;
if(press_button() == 2) {
nb--;
in[i] = false;
outside(i);
}
}
return nb;
}
int min_cardinality(int n) {
in.resize(n);
alive.resize(n);
int nbAlive = n;
for(int i = 0; i < n; i++) alive[i] = true;
int nbType = getNbType(n),
majorant = 1000*1000, suppr = 0;
while(majorant * nbType > nbAlive) {
int test = nbAlive / nbType;
for(int i = 0; i < n; i++)
if(alive[i]) {
inside(i);
if(press_button() > test)
outside(i);
}
if(nbInside == nbType * test) {
suppr += test;
majorant -= test;
for(int i = 0; i < n; i++)
if(in[i]) {
alive[i] = false;
nbAlive--;
}
} else {
majorant = test;
for(int i = 0; i < n; i++)
if(!in[i] && alive[i]) {
alive[i] = false;
nbAlive--;
}
}
nbType = getNbType(n);
}
return majorant + suppr;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |