Submission #1232434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232434		inesfi	Rarest Insects (IOI22_insects)	C++20	0 / 100	32 ms	424 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;

// void move_inside(int i)
// void move_outside(int i)
// int press_button()

const int TAILLEMAXI=2002;
int prenable[TAILLEMAXI];
int deja[TAILLEMAXI];
int nbgroupes;

int min_cardinality(int N) {
    nbgroupes=1;
    deja[0]=1;
    move_inside(0);
    for (int i=1;i<N;i++){
        move_inside(i);
        if (press_button()==1){
            prenable[i]=1;
            nbgroupes++;
            deja[i]=1;
        }
        else {
            move_outside(i);
        }
    }
    int nbdedans=nbgroupes;
    int g=1,d=N/nbgroupes;
    while (g<d){
        int m=(g+d+1)/2;
        for (int i=0;i<N;i++){
            if (prenable[i]==0 and deja[i]==0){
                move_inside(i);
                if (press_button()>m){
                    move_outside(i);
                }
                else {
                    deja[i]=1;
                    nbdedans++;
                }
            }
        }
        if (nbdedans==m*nbgroupes){
            g=m;
            for (int i=0;i<N;i++){
                if (deja[i]==1){
                    prenable[i]=1;
                }
            }
        }
        else {
            d=m-1;
            for (int i=0;i<N;i++){
                if (deja[i]==1 and prenable[i]==0){
                    move_outside(i);
                    prenable[i]=1;
                    nbdedans--;
                }
            }
        }
    }
    return g;
}

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