Submission #639072

#	Time	Username	Problem	Language	Result	Execution time	Memory
639072		dxz05	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	196 ms	432 KiB

insects

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

using namespace std;

int min_cardinality(int N) {
    int diff = 0;
    vector<int> in, out;
    for (int i = 0; i < N; i++) {
        move_inside(i);
        if (press_button() == 1) {
            diff++;
            in.push_back(i);
        } else {
            move_outside(i);
            out.push_back(i);
        }
    }

    vector<int> insects(N);
    iota(insects.begin(), insects.end(), 0);

    int l = 1, r = N / diff;
    while (l <= r){
        int m = (l + r) >> 1;

        in.clear(); out.clear();
        for (int i : insects) {
            move_inside(i);
            if (press_button() <= m){
                in.push_back(i);
            } else {
                move_outside(i);
                out.push_back(i);
            }
        }

        bool check = ((int)in.size() == m * diff);

        if (check){
            l = m + 1;
        } else {
            r = m - 1;
            insects = in;
            for (int i : insects){
                move_outside(i);
                out.push_back(i);
            }
        }
    }

    return l - 1;
}

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