Submission #1080676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080676		asdasdqwer	Rarest Insects (IOI22_insects)	C++17	10 / 100	277 ms	600 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>
using namespace std;

int one(int n, vector<int> &idx) {
    vector<bool> vis(n, false);
    for (auto &x:idx) {
        vis[x]=true;
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> rd;
    for (int i=0;i<n;i++) {
        rd.push_back(i);
    }

    shuffle(rd.begin(), rd.end(), rng);

    int mn = 1e9;
    int sm = 0;
    idx.pop_back();

    for (auto &x:idx) {
        int sz=1;
        move_inside(x);
        for (int i:rd) {
            if (vis[i]) continue;
            move_inside(i);
            
            if (press_button() == 2) {
                vis[i]=true;
                sz++;
            }

            move_outside(i);
        }

        if (sz == 1) {
            return sz;
        }

        mn = min(mn, sz);
        sm += sz;

        move_outside(x);
    }

    return min(mn, n-sm);
}

// int two(int n, vector<int> &idx) {

// }

int min_cardinality(int N) {
    // first all distinct
    vector<int> idx = {0};
    move_inside(0);
    int sz = 1;
    for (int i=1;i<N;i++) {
        move_inside(i);
        if (press_button() == 2) {
            move_outside(i);
        }

        else {
            sz++;
            idx.push_back(i);
        }
    }

    if (sz == N) {
        return 1;
    }

    if (sz == 1) {
        return N;
    }

    for (int i=0;i<sz;i++) {
        move_outside(idx[i]);
    }

    return one(N, idx);


}

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