Submission #652946

#	Time	Username	Problem	Language	Result	Execution time	Memory
652946		grt	Rarest Insects (IOI22_insects)	C++17	99.76 / 100	64 ms	428 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, ans;

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();
                }
        }
        for(int x : taken) {
                move_outside(x);
                discarded[x] = true;
        }
        return (int)taken.size();
}

bool mark[nax];

void elimination(vi &v, int lim) {
        for(int x : v) mark[x] = false;
        vi taken = {};
        shuffle(v.begin(), v.end(), rng);
        for(int x : v) {
                move_inside(x);
                taken.PB(x);
                if(press_button() > lim) {
                        move_outside(x);
                        taken.pop_back();
                }
        }
        for(int x : taken) {
                move_outside(x);
                mark[x] = true;
        }
        if((int)taken.size() == k * lim) {
                for(int x : taken) {
                        discarded[x] = true;
                }
                ans += lim;
        } else {
                for(int x : v) {
                        if(!mark[x]) discarded[x] = true;
                }
        }
}


int min_cardinality(int n) {
        vi allowed = {};
        for(int i = 0; i < n; ++i) {
                allowed.PB(i);
        }
        k = n;
        k = baseLength(allowed);
        ans = 1;
        while(true) {
                allowed = {};
                for(int i = 0; i < n; ++i) {
                        if(!discarded[i]) {
                                allowed.PB(i);
                        }
                }
                if(k > (int)allowed.size()) {
                        return ans;
                }
                int B = (int)allowed.size() / k;
                B /= 2;
                B = max(B, 1);
                elimination(allowed, B);
        }
        return -1;
}

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