Submission #1261185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261185		xtl	Rarest Insects (IOI22_insects)	C++20	0 / 100	98 ms	320 KiB

insects

#include <bits/stdc++.h>
using namespace std;
vector<int> inside;
unordered_set<int> sett;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N)
{
    // number of different types
    for (int i = 0; i < N; i++)
    {
        move_inside(i);
        if (press_button() > 1)
        {
            move_outside(i);
            sett.insert(i);
        }
        else
            inside.push_back(i);
    }
    int l = 1;
    int r = N / inside.size();
    // binary search
    while (l < r)
    {
        int m = (l + r) / 2;
        vector<int> w;
        vector<int> outs;
        for (int i : sett)
        {
            move_inside(i);
            if (press_button() > m)
            {
                move_outside(i);
                outs.push_back(i);
            }
            else
                w.push_back(i);
        }
        if (w.size() == inside.size() * (m - l))
        {
            l = m;
            for (int i : w)
                sett.erase(i);
        }
        else
        {
            for (int i : outs)
                sett.erase(i);
            for (int i : w)
                move_outside(i);
            r = m - 1;
        }
    }
    return l;
}

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