Submission #1232457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232457		inesfi	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	27 ms	428 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) {
    fill(prenable, prenable + TAILLEMAXI, 0);
    fill(deja, deja + TAILLEMAXI, 0);
    nbgroupes = 0;

    for (int i=0;i<N;i++){
        move_inside(i);
        cerr << "in " << i << endl;
        if (nbgroupes==0 or press_button()==1){
            prenable[i]=1;
            nbgroupes++;
            deja[i]=1;
        }
        else {
            move_outside(i);
            cerr << "out " << i << endl;
        }
    }
    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);
                cerr << "in " << i << endl;

                if (press_button()>m){
                    move_outside(i);
                    cerr << "out " << i << endl;
                }
                else {
                    deja[i]=1;
                    nbdedans++;
                }
            }
        }
        cerr << nbdedans << " " << nbgroupes << " " << m << " ";
        if (nbdedans==m*nbgroupes){
            cerr << "lft" << endl;
            g=m;
            for (int i=0;i<N;i++){
                if (deja[i]==1){
                    prenable[i]=1;
                }
            }
        }
        else {
            cerr << "rgt" << endl;
            d=m-1;
            for (int i=0;i<N;i++){
                if (deja[i]==0) prenable[i] = 1;
            }

            for (int i=0;i<N;i++){
                if (deja[i]==1 and prenable[i]==0){
                    move_outside(i);
                    cerr << "out " << i << endl;
                    deja[i]=0;
                    nbdedans--;
                }
            }
        }
    }
    return g;
}

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