Submission #1244291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244291		badge881	Rarest Insects (IOI22_insects)	C++20	65.51 / 100	38 ms	448 KiB

insects

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

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

int get_random(int range)
{
    return (abs((long long)rng_engine()) % range) + 1;
}

vector<int> current_set;
int total_elements;

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

void insert_element(int index)
{
    if (find(current_set.begin(), current_set.end(), index) != current_set.end())
        return;
    move_inside(index);
    current_set.push_back(index);
}

void remove_element(int index)
{
    auto it = find(current_set.begin(), current_set.end(), index);
    if (it == current_set.end())
        return;
    move_outside(index);
    current_set.erase(it);
}

int press()
{
    return press_button();
}

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

int min_cardinality(int N)
{
    total_elements = N;
    vector<int> all_elements, last_state;
    bool using_last_state = true;

    for (int i = 0; i < N; ++i)
    {
        insert_element(i);
        all_elements.push_back(i);
        if (i > 0 && press() > 1)
            remove_element(i);
    }

    int base = current_set.size();
    last_state = current_set;

    if (base == 1)
        return N;

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

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

        shuffle_elements(all_elements);

        if (!using_last_state)
            for (int x : all_elements)
                if (find(last_state.begin(), last_state.end(), x) == last_state.end())
                    remove_element(x);

        for (int i = 0; i < all_elements.size(); ++i)
        {
            if ((int)current_set.size() == base * mid)
                break;

            insert_element(all_elements[i]);

            if ((int)current_set.size() > base * mid || press() > mid)
                remove_element(all_elements[i]);
        }

        if ((int)current_set.size() == base * mid)
        {
            low = mid;
            last_state = current_set;
            using_last_state = true;
        }
        else
        {
            high = mid;
            all_elements = current_set;
            using_last_state = false;
        }
    }

    current_set.clear();
    return low;
}

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