Submission #1240367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240367		Hamed_Ghaffari	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	416 KiB

insects

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

const int MXN = 2008;

bool del[MXN];
int mark[MXN], timer=1;

int min_cardinality(int n) {
    int dif=0;
    for(int i=0; i<n; i++) {
        move_inside(i);
        mark[i] = 1;
        if(press_button()==2) {
            move_outside(i);
            mark[i] = 0;
        }
        else dif++;
    }
    if(dif==1) return n;
    int l=1, r=n/dif+1, mid, cnt;
    while(r-l>1) {
        timer++;
        mid = (l+r)>>1;
        for(int i=0; i<n; i++) if(!mark[i] && !del[i]) {
            move_inside(i);
            mark[i] = timer;
            cnt++;
            if(cnt>mid && press_button()>mid) {
                move_outside(i);
                mark[i] = 0;
                cnt--;
            }
        }
        if(1ll*mid*dif==cnt)
            l = mid;
        else {
            r = mid;
            for(int i=0; i<n; i++)
                if(!mark[i])
                    del[i] = 1;
            for(int i=0; i<n; i++)
                if(mark[i]==timer)
                    move_outside(i),
                    mark[i] = 0,
                    cnt--;
        }
    }
    return l;
}

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