Submission #1247722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247722		DeathIsAwe	Rarest Insects (IOI22_insects)	C++20	47.50 / 100	67 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
int n;


void clean(vector<int> &arr) {
    for (int i: arr) {
        move_outside(i);
    }
    arr.clear();
}


int min_cardinality(int N) {
    int numtype = 0, size = 0;
    n = N;
    vector<int> curarr;
    for (int i=0;i<n;i++) {
        move_inside(i);
        numtype += 1;
        curarr.pb(i);
        if (press_button() > 1) {
            move_outside(i);
            numtype -= 1;
            curarr.pop_back();
        }
    }
    clean(curarr);


    int top = n + 1, bottom = 1, mid;
    while (top > bottom + 1) {
        mid = (top + bottom) / 2;
        for (int i=0;i<n;i++) {
            move_inside(i);
            curarr.pb(i);
            if (press_button() > mid) {
                move_outside(i);
                curarr.pop_back();
            }
        }
        if (curarr.size() == numtype * mid) {
            bottom = mid;
        } else {
            top = mid;
        }
        clean(curarr);
    }
    return bottom;
}

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