Submission #884266

#	Time	Username	Problem	Language	Result	Execution time	Memory
884266		abcvuitunggio	Rarest Insects (IOI22_insects)	C++17	100 / 100	32 ms	856 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
int idx[2001],state[2001],a[2001],cnt,cur;
int min_cardinality(int n){
    std::iota(idx,idx+n,0);
    std::random_shuffle(idx,idx+n);
    for (int i=0;i<n;i++){
        move_inside(idx[i]);
        state[i]=1;
        a[i]=press_button();
        if (a[i]>1){
            move_outside(idx[i]);
            state[i]=0;
        }
        else
            cnt++;
    }
    cur=cnt;
    int l=2,r=n/cnt,kq=1;
    while (l<=r){
        int mid=(l+r)>>1;
        int mx=0;
        for (int i=0;i<n;i++)
            if (state[i]&&a[i]>mid){
                move_outside(idx[i]);
                cur--;
                state[i]=0;
                if (a[i]>mx)
                    mx=a[i];
                else
                    a[i]=0;
            }
        for (int i=0;i<n&&cur<mid*cnt;i++){
            if (state[i]||a[i]>mid)
                continue;
            move_inside(idx[i]);
            a[i]=press_button();
            if (a[i]>mid)
                move_outside(idx[i]);
            else{
                cur++;
                state[i]=1;
            }
        }
        if (cur==mid*cnt){
            kq=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return kq;
}

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