Submission #884258

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

insects

#include "insects.h"
int state[2001],a[2001],cnt,cur;
int min_cardinality(int n){
    for (int i=0;i<n;i++){
        move_inside(i);
        state[i]=1;
        a[i]=press_button();
        if (a[i]>1){
            move_outside(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(i);
                cur--;
                state[i]=0;
                if (a[i]>mx)
                    mx=a[i];
                else
                    a[i]=0;
            }
        for (int i=0;i<n;i++){
            if (state[i]||a[i]>mid)
                continue;
            move_inside(i);
            a[i]=press_button();
            if (a[i]>mid)
                move_outside(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: 74.89 / 75