Submission #780677

#	Time	Username	Problem	Language	Result	Execution time	Memory
780677		mousebeaver	Rarest Insects (IOI22_insects)	C++17	79.68 / 100	113 ms	456 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
#define pii pair<int, int>
using namespace std;

set<pii> inside;
set<pii> outside; //Random key, insect index
int types = -1;

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

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

    return inside.size();
}

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

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

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

int min_cardinality(int N)
{
    srand(42);
    for(int i = 0; i < N; i++)
    {
        outside.insert({rand()%100000, i});
    }

    types = countTypes();
    if(types <= 5)
    {
        while(inside.size())
        {
            move_outside((*inside.begin()).second);
            outside.insert(*inside.begin());
            inside.erase(inside.begin());            
        }
        vector<int> a(N);
        int counter = 0;
        for(pii p : outside)
        {
            a[counter] = p.second;
            counter++;
        }
        vector<int> card(N, -1);
        for(int i = 0; i < N; i++)
        {
            if(card[a[i]] == -1)
            {
                move_inside(a[i]);
                vector<int> machine = {a[i]};
                for(int j = i+1; j < N; j++)
                {
                    if(card[a[j]]  == -1)
                    {
                        move_inside(a[j]);
                        machine.push_back(a[j]);
                        int state = press_button();
                        if(state != (int) machine.size())
                        {
                            move_outside(a[j]);
                            machine.pop_back();
                        }
                    }
                }
                for(int j : machine)
                {
                    card[j] = machine.size();
                    move_outside(j);
                }
            }
        }
    
        return *min_element(card.begin(), card.end());
    }
    int left = 1;
    int right = N/types;

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

    return left;
}

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