Submission #1158306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158306		Math4Life2020	Rarest Insects (IOI22_insects)	C++20	88.21 / 100	26 ms	556 KiB

insects

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

int min_cardinality(int N) {
    set<ll> cnums;
    for (ll i=0;i<N;i++) {
        cnums.insert(i);
    }
    vector<ll> currin;
    for (ll x: cnums) {
        move_inside(x);
        if (press_button()>1) {
            move_outside(x);
        } else {
            currin.push_back(x);
        }
    }
    ll nterms = currin.size();
    for (ll x: currin) {
        move_outside(x);
    }
    while (1) {
        ll qn = cnums.size()/nterms;
        vector<ll> vdisc; //discard
        vector<ll> vin;
        for (ll x: cnums) {
            move_inside(x);
            if (press_button()>=qn) {
                move_outside(x);
                vdisc.push_back(x);
            } else {
                vin.push_back(x);
            }
        }
        for (ll x: vin) {
            move_outside(x);
        }
        set<ll> nnums;
        ll NDEL = 0;
        for (ll y: vdisc) {
            move_inside(y);
            if (press_button()>1) {
                move_outside(y);
            } else {
                NDEL++;
            }
        }
        for (ll y: vin) {
            move_inside(y);
            if (press_button()==1) {
                nnums.insert(y);
            }
            move_outside(y);
        }
        nterms -= NDEL;
        if (nterms == 0) {
            return qn;
        }
        cnums = nnums;
    }
}

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