Submission #1226619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226619		hengliao	Rarest Insects (IOI22_insects)	C++20	99.78 / 100	15 ms	436 KiB

insects

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef int ll;

int min_cardinality(int n) {
    vector<bool> done(n);
    ll siz=0;

    auto in=[&](ll tar){
        move_inside(tar);
        done[tar]=1;
        siz++;
    };

    auto out=[&](ll tar){
        move_outside(tar);
        done[tar]=0;
        siz--;
    };

    auto press=[&](){
        return press_button();
    };

    for(ll i=0;i<n;i++){
        in(i);
        if(press()>1){
            out(i);
        }
    }

    ll ty=siz;

    if(ty==n) return 1;

    for(ll i=0;i<n;i++){
        if(done[i]) out(i);
    }

    vll a(n);

    ll lef=2, rig=n/ty;
    ll good=-1;

    auto check=[&](ll tar){
        vll v;
        for(ll i=0;i<n;i++){
            if(a[i]>tar && done[i]){
                v.pb(i);
            }
            else if(a[i]<=tar && !done[i]){
                v.pb(i);
            }
        }
        for(auto &it:v){
            if(done[it]) out(it);
        }
        for(auto &it:v){
            in(it);
            a[it]=press();
            if(a[it]>tar){
                out(it);
            }
        }
        return siz>=tar*ty;
    };

    while(lef<=rig){
        ll mid=(lef+rig)/2;
        if(check(mid)){
            good=mid;
            lef=mid+1;
        }
        else{
            rig=mid-1;
        }
    }

    if(good==-1) return 1;

    return good;
}

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