Submission #786170

#	Time	Username	Problem	Language	Result	Execution time	Memory
786170		vjudge1	Rarest Insects (IOI22_insects)	C++17	10 / 100	273 ms	208 KiB

insects

#include <bits/stdc++.h>

using namespace std;
void move_inside(int);
void move_outside(int);
int press_button();

int min_cardinality(int N)
{
        vector<int> types(N, -1);
        int t = 0;
        for (int i = 0; i < N - 1; i++) {
                if (types[i] != -1)
                        continue;
                types[i] = t;
                move_inside(i);
                for (int j = i + 1; j < N; j++) {
                        if (types[j] != -1)
                                continue;
                        move_inside(j);
                        int ret = press_button();
                        if (ret > 1)
                                types[j] = t;
                        move_outside(j);
                }
                move_outside(i);
                t++;
        }
        if (types[N - 1] == -1) {
                types[N - 1] = t;
                t++;
        }
        vector<int> cnt(t);
        for (int i = 0; i < N; i++)
                cnt[types[i]]++;
        int mn = cnt[0];
        for (auto x : cnt)
                if (x < mn)
                        mn = x;
        return mn;
}

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