Submission #1244385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244385		badge881	Rarest Insects (IOI22_insects)	C++20	100 / 100	17 ms	472 KiB

insects

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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand_index(int n) {
    return abs((ll)rng()) % n + 1;
}

vector<int> current;
int total;

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

void insert(int i) {
    for (int x : current)
        if (x == i) return;
    move_inside(i);
    current.push_back(i);
}

void erase(int i) {
    auto it = find(current.begin(), current.end(), i);
    if (it != current.end()) {
        move_outside(i);
        current.erase(it);
    }
}

int press() {
    return press_button();
}

void shuffle_vec(vector<int>& v) {
    for (int i = 0; i < v.size(); ++i)
        swap(v[i], v[rand_index(v.size()) - 1]);
}

int min_cardinality(int N) {
    total = N;
    vector<int> pool, stable;
    bool keep = true;

    for (int i = 0; i < total; ++i) {
        insert(i);
        pool.push_back(i);
        if (i && press() > 1)
            erase(i);
    }

    int base = current.size();
    stable = current;

    if (base == 1) {
        current.clear();
        return total;
    }

    int low = 1, high = total / base + 1;

    while (low + 1 < high) {
        int mid = (low + high) / 2;
        shuffle_vec(pool);

        if (!keep) {
            for (int x : pool)
                if (find(stable.begin(), stable.end(), x) == stable.end())
                    erase(x);
        }

        for (int i = 0; i < pool.size(); ++i) {
            if ((int)current.size() == base * mid) break;
            int before = current.size();
            insert(pool[i]);
            if ((int)current.size() > before && press() > mid)
                erase(pool[i]);
        }

        if ((int)current.size() == base * mid) {
            low = mid;
            stable = current;
            keep = true;
        } else {
            high = mid;
            pool = current;
            keep = false;
        }
    }

    current.clear();
    return low;
}

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