Submission #783161

#	Time	Username	Problem	Language	Result	Execution time	Memory
783161		mousebeaver	Rarest Insects (IOI22_insects)	C++17	70.08 / 100	128 ms	464 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 offset = 0;
     
    int countTypes()
    {
        int pb = press_button();
        while(inside.size() && pb > 1)
        {
            for(int i = pb; i > 1; i--)
            {
                move_outside((*inside.begin()).second);
                outside.insert(*inside.begin());
                inside.erase(inside.begin());
            }
            pb = press_button();
        }
     
        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 && 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?
    {
        int pb = press_button();
        while(pb > k)
            {
                for(int i = pb; i > k; i--)
                {
                    move_outside((*inside.begin()).second);
                    outside.insert(*inside.begin());
                    inside.erase(inside.begin());
                }
                pb = press_button();
            }
     
        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(43);
        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);
            int lastcounter = 0;
            for(int i = 0; i < N; i++)
            {
                if(types > 1 && card[a[i]] == -1)
                {
                    types--;
                    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);
                    }
                }
                else if(card[a[i]] == -1)
                {
                    lastcounter++;
                }
            }
            for(int i = 0; i < N; i++)
            {
                card[i] = (card[i] == -1 ? lastcounter : card[i]);
            }
        
            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 > 10)
            {
                mid = left + (right-left)/6;
            }
            if(test(mid))
            {
                if(right+1-(right-left)/4 < mid)
                {
                    offset += mid;
                    while(inside.size())
                    {
                        move_outside((*inside.begin()).second);
                        inside.erase(inside.begin());
                    }
                    if(countTypes() < types)
                    {
                        return offset;
                    }
                    right = right-mid;
                    left = 1;
                }
                else
                {
                    left = mid;
                }
            }
            else
            {
                right = mid-1;
            }
        }
     
        return left+offset;
    }

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