Submission #1247733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247733		DeathIsAwe	Rarest Insects (IOI22_insects)	C++20	96.24 / 100	19 ms	432 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;
bool banned[2000];


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


int min_cardinality(int N) {
    int numtype = 0, size = 0, ansbuffer = 0, bannednum = 0;
    n = N;
    for (int i=0;i<n;i++) {
        banned[i] = false;
    }
    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();
        }
    }
    for (int i: curarr) {banned[i] = true; bannednum += 1;}
    ansbuffer = 1;
    clean(curarr);


    int top = n, mid;
    vector<int> temp;
    while (top > 1) {
        mid = top / 2;
        if (mid * numtype > n - bannednum) {
            top = mid;
            continue;
        }
        for (int i=0;i<n;i++) {
            if (banned[i]) continue;
            move_inside(i);
            curarr.pb(i);
            if (press_button() > mid) {
                move_outside(i);
                temp.pb(i);
                curarr.pop_back();
            }
        }
        if (curarr.size() == numtype * mid) {
            for (int i: curarr) {banned[i] = true; bannednum += 1;}
            ansbuffer += mid;
            top = top - mid;
        } else {
            top = mid;
            for (int i: temp) {banned[i] = true; bannednum += 1;}
        }
        temp.clear();
        clean(curarr);
    }
    return ansbuffer;
}

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