Submission #1229308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229308		LucaIlie	Rarest Insects (IOI22_insects)	C++20	96.45 / 100	15 ms	436 KiB

insects

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

using namespace std;

const int MAX_N = 2e3;
int n;
bool getout[MAX_N];
vector<int> distinct, insects;
mt19937 rnd(100111);

int min_cardinality(int N) {
    n = N;

    move_inside(0);
    distinct.push_back(0);
    for (int i = 1; i < n; i++) {
        move_inside(i);
        if (press_button() == 2) {
            move_outside(i);
            insects.push_back(i);
        }
        else
            distinct.push_back(i);
    }
    int t = distinct.size();

    int l = 1, r = n / t + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        int k = l * t;
        int maxP = 0;
        vector<int> remInsects, elimInsects;
        for (int i: insects) {
            move_inside(i);
            getout[i] = true;
            int p = press_button();
            if (p > mid) {
                move_outside(i);
                elimInsects.push_back(i);
            }
            else {
                k++;
                maxP = max(maxP, p);
                remInsects.push_back(i);
            }
        }

        // printf("%d %d\n", mid, k);

        if (k < mid * t) {
            r = maxP;
            for (int i: insects) {
                if (getout[i]) 
                    move_outside(i);
                getout[i] = false;
            }   
            insects = remInsects;
        }
        else {
            l = mid;
            insects = elimInsects;
        }
    }

    return l;
}

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