Submission #979657

#	Time	Username	Problem	Language	Result	Execution time	Memory
979657		12345678	Rarest Insects (IOI22_insects)	C++17	100 / 100	33 ms	1268 KiB

insects

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

using namespace std;

const int nx=2e3+5;

mt19937 rng(time(0));

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

vector<pair<int, int>> v;

int min_cardinality(int N) {
    cin.tie(NULL)->sync_with_stdio(false);
    for (int i=0; i<N; i++) v.push_back({rng(), i});
    sort(v.begin(), v.end());
    for (int i=0; i<N; i++) p[v[i].second]=i;
    for (int i=0; i<N; i++)
    {
        move_inside(p[i]);
        if (press_button()==1) cnt++, in[i]=1, s[i]=1;
        else move_outside(p[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(p[i]);
            if (press_button()>md) move_outside(p[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(p[i]), sz--;
        }
    }
    return l;
}

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