Submission #627461

#	Time	Username	Problem	Language	Result	Execution time	Memory
627461		I_love_Hoang_Yen	Rarest Insects (IOI22_insects)	C++17	10 / 100	368 ms	416 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
#define SZ(s) ((int) s.size())
using namespace std;

int min_cardinality(int n) {
    std::vector<int> v_ids(n);
    std::iota(v_ids.begin(), v_ids.end(), 0);

    std::set<int> ids(v_ids.begin(), v_ids.end());
    int freq = 0, last_cnt = 0;

    while (true) {
        ++freq;
        std::set<int> new_ids;

        for (int id : ids) {
            move_inside(id);
            if (press_button() > freq) {
                move_outside(id);
                new_ids.insert(id);
            }
        }

        int unique_values = SZ(ids) - SZ(new_ids);
        if (unique_values < last_cnt) {
            return freq - 1;
        }
        last_cnt = unique_values;

        if (unique_values > SZ(new_ids)) {
            return freq;
        }

        ids = std::move(new_ids);
    }

    return 0;
}

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