Submission #766374

#	Time	Username	Problem	Language	Result	Execution time	Memory
766374		adrilen	Rarest Insects (IOI22_insects)	C++17	99.89 / 100	59 ms	440 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

constexpr int maxn = 2e3 + 9;

bool removed[maxn] = { 0 };

vector <int> in_machine;

mt19937 rng(120349812034);

int min_cardinality(int n) {

    vector <int> m(n);
    for (int i = 0; i < n; i++) m[i] = i;
    shuffle(m.begin(), m.end(), rng);

    // Find group

    for (int i = 0; i < n; i++)
    {
        move_inside(i);
        if (press_button() > 1) {
            move_outside(i);
        } else {
            in_machine.emplace_back(i);
            removed[i] = true;
        }
    }

    int g = in_machine.size();

    int l = 1, r = n / g;
    int mid;
    while (l != r)
    {
        mid = (l + r + 1) >> 1;


        vector <int> taken_out, taken_in;

        int i;
        for (int y = 0; y < n; y++)
        {
            i = m[y];
            if (removed[i]) continue;

            move_inside(i);
            if (press_button() > mid) {
                taken_out.emplace_back(i);
                move_outside(i);
            } else {
                taken_in.emplace_back(i);
                in_machine.emplace_back(i);
            }
        }

        
        if ((int)in_machine.size() == mid * g)
        {
            // Mid is lowerbound
            l = mid;

            for (int i : taken_in) removed[i] = true;
        } else {
            r = mid - 1;

            for (int i : taken_out) removed[i] = true;
            for (int i : taken_in) {
                move_outside(i);
                in_machine.pop_back();
            }
        }
    }


    return l;
}

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