Submission #780584

#	Time	Username	Problem	Language	Result	Execution time	Memory
780584		mousebeaver	Rarest Insects (IOI22_insects)	C++17	0 / 100	1 ms	336 KiB

insects

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

set<int> inside;
set<int> outside;
int types = -1;

int countTypes()
{
    while(inside.size() && press_button() > 1)
    {
        move_outside(*inside.begin());
        outside.insert(*inside.begin());
        inside.erase(inside.begin());
    }

    vector<int> a(0);
    for(int i : outside)
    {
        a.push_back(i);
    }
    for(int i : a)
    {
        move_inside(i);
        inside.insert(i);
        outside.erase(i);
        if(inside.size() > 1)
        {
            if(press_button() > 1)
            {
                move_outside(i);
                outside.insert(i);
                inside.erase(i);
            }
        }
    }

    return outside.size();
}

bool test(int k) //Every type at least k insects?
{
    while(press_button() > k)
    {
        move_outside(*outside.begin());
        outside.erase(outside.begin());
    }

    vector<int> a(0);
    for(int i : outside)
    {
        a.push_back(i);
    }
    for(int i : a)
    {
        move_inside(i);
        inside.insert(i);
        outside.erase(i);
        if((int) inside.size() > k)
        {
            if(press_button() > k)
            {
                move_outside(i);
                outside.insert(i);
                inside.erase(i);
            }
        }
    }

    return((int) inside.size() == k*types);
}

int min_cardinality(int N)
{
    for(int i = 0; i < N; i++)
    {
        outside.insert(i);
    }

    types = countTypes();
    int left = 1;
    int right = N/types;

    while(left < right)
    {
        int mid = (left+right+1)/2;
        if(test(mid))
        {
            left = mid;
        }
        else
        {
            right = mid-1;
        }
    }

    return left;
}

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