Submission #967932

#	Time	Username	Problem	Language	Result	Execution time	Memory
967932		12345678	Rarest Insects (IOI22_insects)	C++17	50 / 100	109 ms	1588 KiB

insects

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

using namespace std;

int p, cnt, sz;
vector<int> v;

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++, v.push_back(i);
        else move_outside(i);
    }
    for (auto x:v) move_outside(x);
    if (cnt==1) return N;
    int l=1, r=N/cnt;
    while (l<r)
    {
        int md=(l+r+1)/2;
        sz=0;
        v.clear();
        for (int i=0; i<N; i++)
        {
            move_inside(i);
            if (press_button()>md) move_outside(i);
            else sz++, v.push_back(i);
        }
        if (sz==cnt*md) l=md;
        else r=md-1;
        for (auto x:v) move_outside(x);
    }
    return l;
}

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