Submission #1212562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212562		qwusha	Rarest Insects (IOI22_insects)	C++20	10 / 100	99 ms	412 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e9;


int min_cardinality(int n) {
    vector<int> par(n, -1);
    bool ok = 1;
    while (ok) {
        ok = 0;
        int st = -1;
        for (int i = 0; i < n; i++) {
            if (par[i] == -1) {
                ok = 1;
                st = i;
                break;
            }
        }
        if (!ok)
            break;
        par[st] = st;
        move_inside(st);
        int cur = 1;
        for (int i = st + 1; i < n; i++) {
            if (par[i] == -1) {
                move_inside(i);
                int x = press_button();
                if (x == cur) {
                    move_outside(i);
                } else {
                    cur = x;
                    par[i] = st;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (par[i] == st) {
                move_outside(i);
            }
        }
    }
    vector<int> cnt(n);
    for (int i = 0; i < n; i++) {
        cnt[par[i]]++;
    }
    int mini = inf;
    for (int i = 0; i < n; i++) {
        if (cnt[i] > 0) {
            mini = min(mini, cnt[i]);
        }
    }
    return mini;
}

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