Submission #652941

#	Time	Username	Problem	Language	Result	Execution time	Memory
652941		grt	Rarest Insects (IOI22_insects)	C++17	90.87 / 100	99 ms	332 KiB

insects

#include "insects.h"
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 2010;
bool discarded[nax];

mt19937 rng(104910);
int k;

int baseLength(vi &v) {
        vi taken = {};
        shuffle(v.begin(), v.end(), rng);
        for(int x : v) {
                move_inside(x);
                taken.PB(x);
                int w = press_button();
                if(w >= 2) {
                        move_outside(x);
                        taken.pop_back();
                }
                if((int)taken.size() == k) {
                        break;
                }
        }
        for(int x : taken) {
                move_outside(x);
                discarded[x] = true;
        }
        return (int)taken.size();
}


int min_cardinality(int n) {
        vi allowed = {};
        for(int i = 0; i < n; ++i) {
                allowed.PB(i);
        }
        k = n;
        k = baseLength(allowed);
        for(int i = 2; i <= n; ++i) {
                allowed.clear();
                for(int j = 0; j < n; ++j) {
                        if(!discarded[j]) {
                                allowed.PB(j);
                        }
                }
                int k2 = baseLength(allowed);
                if(k2 < k) {
                        return i - 1;
                }
        }
        return n;
}

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