Submission #1054776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054776		mc061	Rarest Insects (IOI22_insects)	C++17	98.10 / 100	43 ms	700 KiB

insects

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

void move_inside(int i);
void move_outside(int i);
int press_button();

const int mN = 5000;
bool diff[mN]={};

int r[mN]={};

int min_cardinality(int n) {
    srand(time(0));
    iota(r, r+n, 0);
    // random_shuffle(r, r+n);
    vector<int> diffs;
    for (int i = 0; i < n; ++i) {
        move_inside(r[i]);
        diffs.push_back(r[i]);
        int x = press_button();
        if (x == 2) {
            move_outside(r[i]);
            diffs.pop_back();
        }
    }

    int biggest_ans = n/diffs.size();

    for (int i : diffs) move_outside(i), diff[i] = true;

    vector<int> out;
    vector<int> cur_in;
    for (int i = 0; i < n; ++i) {
        if (diff[r[i]]) continue;
        out.push_back(r[i]);
    }

    int cursz = 0;
    auto fill_gap = [&] (int newsz) {
        vector<int> nout;
        for (int i : out) {
            move_inside(i);
            cur_in.push_back(i);
            if (press_button() >= newsz) {
                nout.push_back(i);
                move_outside(i);
                cur_in.pop_back();
            }
        }
        out.swap(nout);
        cursz = newsz;
    };

    int low = 1, high = biggest_ans;
    while (high != low) {
        int mid = (high+low+1) >> 1;
        if (mid < cursz) {
            while (cur_in.size()) {
                out.push_back(cur_in.back());
                move_outside(cur_in.back());
                cur_in.pop_back();
                if (press_button() < mid) break;
            }
            cursz = mid-1;
        }
        fill_gap(mid);
        vector<int> ndiffs;
        for (int j : diffs) {
            move_inside(j);
            if (press_button() < mid) {
                ndiffs.push_back(j);
            }
            move_outside(j);
        }
        if (ndiffs.size() == 0) low = mid;
        else {
            high = mid-1, ndiffs.swap(diffs);
            out.clear();
        }
    }
    return low;
}

/*
90
6 8 2 9 4 4 2 2 8 5 5 2 4 9 10 3 0 7 10 2 3 10 3 5 1 0 4 4 10 1 9 5 6 9 10 9 9 7 1 4 8 8 6 4 3 6 3 2 10 7 0 7 2 10 2 4 4 7 3 0 7 5 9 0 6 9 6 7 9 6 2 4 2 7 3 5 2 9 3 10 5 10 4 1 4 5 7 5 9 8 
ans=4
*/

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