Submission #1211979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211979		vivkostov	Rarest Insects (IOI22_insects)	C++20	99.89 / 100	15 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n,br,otg,num;
vector<int>temp,cur,v;
void get_unique()
{
    for(int i=0;i<n;i++)
    {
        move_inside(i);
        br++;
        if(press_button()>1)
        {
            move_outside(i);
            br--;
            cur.push_back(i);
        }
    }
    num=br;
}
int check(int ma)
{
    for(int i=0;i<cur.size();i++)
    {
        move_inside(cur[i]);
        num++;
        if(press_button()>ma)
        {
            temp.push_back(cur[i]);
            move_outside(cur[i]);
            num--;
        }
    }
    if(num/br==ma)return 1;
    return 0;
}
void get_min()
{
    int l=2,r=n/br,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))
        {
            cur=temp;
            l=mid+1;
        }
        else
        {
            if(l==r)break;
            int to=0;
            temp.push_back(-1);
            for(int i=0;i<cur.size();i++)
            {
                if(cur[i]!=temp[to])
                {
                    v.push_back(cur[i]);
                    move_outside(cur[i]);
                    num--;
                }
                else to++;
            }
            cur=v;
            v.clear();
            r=mid-1;
        }
        temp.clear();
        /*cout<<l<<" "<<r<<" | ";
        for(int i=0;i<cur.size();i++)
        {
            cout<<cur[i]<<" ";
        }
        cout<<endl;*/
    }
    otg=l-1;
}
int min_cardinality(int N)
{
    n=N;
    get_unique();
    if(br==1)return N;
    else get_min();
    return otg;
}

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