Submission #979656

#	Time	Username	Problem	Language	Result	Execution time	Memory
979656		12345678	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	32 ms	1100 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int p, cnt, sz, in[nx], t[nx], s[nx];

int min_cardinality(int N) {
    cin.tie(NULL)->sync_with_stdio(false);
    for (int i=0; i<N; i++)
    {
        move_inside(i);
        if (press_button()==1) cnt++, in[i]=1, s[i]=1;
        else move_outside(i);
    }
    if (cnt==1) return N;
    if (cnt==N) return 1;
    int l=1, r=N/cnt;
    sz=cnt;
    while (l<r)
    {
        int md=(l+r+1)/2;
        for (int i=0; i<N; i++)
        {
            if (s[i]||t[i]) continue;
            move_inside(i);
            if (press_button()>md) move_outside(i);
            else sz++, in[i]=1;
            if (sz==cnt*md) break;
        }
        if (sz==cnt*md) 
        {
            l=md;
            for (int i=0; i<N; i++) if (in[i]) s[i]=1;
        }
        else 
        {
            r=md-1;
            for (int i=0; i<N; i++) if (!in[i]) t[i]=1;
            for (int i=0; i<N; i++) if (in[i]&&!s[i]) in[i]=0, move_outside(i), sz--;
        }
    }
    return l;
}

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