Submission #1265744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265744		coderg	Rarest Insects (IOI22_insects)	C++20	100 / 100	15 ms	500 KiB

insects

#include <bits/stdc++.h>
using namespace std;
//#include "insects.h"
vector<int> inside;//almacenar insectos de un tipo completo
set<int> sett;
void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N){
    for (int i = 0; i < N; i++) {
    move_inside(i);
    if (press_button()>1) {  // si hay más de 1 tipo en la camara
        move_outside(i);
        sett.insert(i);
    } else {
        inside.push_back(i);   // pertenece al mismo tipo que los anteriores
    }
}
    int l=1, r=N/inside.size();
    while (l<r){
        int m=l+(r-l+1+(r-l>5))/2;
        vector<int> w;
        vector<int> outs;
        for (auto i:sett) {
         move_inside(i);
       if (press_button()>m) {  // si al agregarlo hay más de m tipos
        move_outside(i);
        outs.push_back(i);
      } else {
        w.push_back(i);        //es valido
    }
}
        // inside.size():cardinalidad del tipo base que tenemos
        // m-l:diferencia entre el valor actual y el anterior
        //inside.size()*(m-l):numero esperado de insectos si todos los tipos tienen al menos 'm' insectos
        if (w.size()==inside.size()*(m-l)){
            l=m;
            for(auto i:w)sett.erase(i);
        }else{
            for(auto i:outs)sett.erase(i);
            for(auto i:w)move_outside(i);
            r=m-1;
        }
    }
    return l;
}

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