Submission #1223515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223515		bangan	Rarest Insects (IOI22_insects)	C++20	10 / 100	99 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int min_cardinality(int N) {
    vector<int> all;
    for (int i=0; i<N; i++) all.pb(i);

    shuffle(all.begin(), all.end(), rng);

    int ans = N;
    while (!all.empty()) {
        vector<int> rem, in;
        int cur = 0;
        while (!all.empty()) {
            int i = all.back();
            all.pop_back();
            move_inside(i);
            int res = press_button();
            if (res == cur) {
                move_outside(i);
                rem.pb(i);
            }
            else {
                in.pb(i);
            }
            cur = res;
        }
        ans = min(ans, cur);
        all = rem;
        shuffle(all.begin(), all.end(), rng);
        for (int IN : in) move_outside(IN);
    }
    return ans;
}

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