Submission #628122

#	Time	Username	Problem	Language	Result	Execution time	Memory
628122		I_love_Hoang_Yen	Rarest Insects (IOI22_insects)	C++17	10 / 100	413 ms	360 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"

#define SZ(s) ((int) s.size())
using namespace std;

#ifndef RR
#define DEBUG(X)
#endif

int min_cardinality(int n) {
    int res = n + 1;  // final result

    // used(i) = true if we already counted species of i
    std::vector<bool> used(n, false);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            // set containing all insects of this species
            std::set<int> same_species {i};
            move_inside(i);

            for (int j = i + 1; j < n; ++j) {
                if (!used[j]) {
                    move_inside(j);
                    if (press_button() == 1 + SZ(same_species)) {
                        same_species.insert(j);
                    } else {
                        move_outside(j);
                    }
                }
            }

            res = std::min(res, SZ(same_species));

            // remove all insects from machine
            for (int j : same_species) {
                move_outside(j);
                used[j] = true;
            }
        }
    }
    return res;
}

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