Submission #628104

#	Time	Username	Problem	Language	Result	Execution time	Memory
628104		I_love_Hoang_Yen	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	208 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) {
    // Step 1: Find a set of indices containing *unique* insects
    std::set<int> uniques;
    for (int i = 0; i < n; ++i) {
        move_inside(i);
        if (press_button() == 2) {
            // i appeared before -> remove it
            move_outside(i);
        } else {
            uniques.insert(i);
        }
    }
    // remove all insects from machine
    for (int i : uniques) {
        move_outside(i);
    }

    // Step 2: For each insect in `uniques`, count how many times it appears
    int res = n + 1;  // final result
    for (int x : uniques) {
        // count how many times x appears
        int cnt = 1;
        for (int i = 0; i < n; ++i) {
            if (i != x) {
                move_inside(i);
                if (press_button() != cnt) {
                    // different species -> remove
                    move_outside(i);
                } else {
                    // same species
                    ++cnt;
                }
            }
        }
        res = std::min(res, cnt);
        // remove all insects from machine
        for (int i = 0; i < n; ++i) {
            move_outside(i);
        }
    }
    return res;
}

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