Submission #1192286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192286		Luvidi	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	17 ms	460 KiB

insects

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

int min_cardinality(int n) {
    int c=0;
    set<int> s,ls;
    for(int i=0;i<n;i++){
        move_inside(i);
        if(press_button()>1){
            move_outside(i);
        }else s.insert(i);
    }
    ls=s;
    set<int> sk;
    c=s.size();
    int l=1,r=n/c;
    while(l<r){
        int m=l+1+(r-l-1)/2;
        set<int> t;
        for(int i=0;i<n;i++)if(!s.count(i)&&!sk.count(i)){
            move_inside(i);
            if(press_button()>m){
                move_outside(i);
                t.insert(i);
            }else s.insert(i);
        }
        if(s.size()/m==c){
            l=m;
            ls=s;
        }else{
            r=m-1;
            for(int i=0;i<n;i++){
                if(s.count(i)&&!ls.count(i)){
                    move_outside(i);
                    s.erase(i);
                }else if(!s.count(i)&&ls.count(i)){
                    move_inside(i);
                    s.insert(i);
                }
            }
            for(int i:t)sk.insert(i);
        }
    }
    return l;
}

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