Submission #1320487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320487		BigBadBully	드문 곤충 (IOI22_insects)	C++20	47.51 / 100	65 ms	536 KiB

insects

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

int min_cardinality(int n) {
    int dst = 0;
    set<int> dists;
    {
    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++,dists.insert(i),hier.insert(i);
        
    }
    for(int x: hier)
        if(!dists.count(x))
            move_outside(x);
    }
    vector<int> lst(n,0);
    function<bool(int)> check = [&](int x)
    {
        if(x>n)return true;
        if(x==0)return false;
        int sz = dst;
        set<int> hier;
        for(int i = 0; i< n; i++)
        {
            if(dists.count(i) || lst[i]>=x)continue;
            move_inside(i);
            int val = press_button();
            if(val>x)
                move_outside(i),lst[i] = max(lst[i],x);
            else
                sz++,hier.insert(i);
        }
        for(int y: hier)
            if(!dists.count(y))
            move_outside(y);
        return sz < x*dst;
    };
    int l = 1,r = n/dst;
    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.51 / 75