Submission #1320476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320476		BigBadBully	Rarest Insects (IOI22_insects)	C++20	0 / 100	5 ms	332 KiB

insects

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

int min_cardinality(int n) {
    int dst = 0;
    for (int i = 0; i < n; i++)
    {
        move_inside(i);
        int val = press_button();
        if(val>1)
            move_outside(i);
        else
            dst++;
    }
    function<bool(int)> check = [&](int x)
    {
        if(x>n)return true;
        if(x==0)return false;
        int sz = 0;
        for(int i = 0; i< n; i++)
        {
            move_inside(i);
            int val = press_button();
            if(val>x)
                move_outside(i);
            else
                sz++;
        }
        return sz < x*dst;
    };
    int l = 2,r = n+1;
    while(r-l)
    {
        int mid = l+r>>1;
        if(check(mid))
            r = mid;
        else
            l = mid+1;
    }
    return l-1;
}

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