Submission #1320479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320479		BigBadBully	드문 곤충 (IOI22_insects)	C++20	47.50 / 100	66 ms	504 KiB

insects

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

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

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