Submission #1240636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240636		someone	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	396 KiB

insects

#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);
            }
        }
    for(int i = 0; i < N; i++)
        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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75