Submission #812730

#	Time	Username	Problem	Language	Result	Execution time	Memory
812730		andrei_boaca	Rarest Insects (IOI22_insects)	C++17	49.74 / 100	147 ms	376 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
int cul[2005];
int n;
vector<int> spec;
struct date
{
    int nod,l,r;
};
vector<date> need;
bool comp(date a, date b)
{
    return a.l<b.l;
}
int f[2005];
int min_cardinality(int N)
{
    n=N;
    cul[0]=1;
    spec.push_back(0);
    move_inside(0);
    int nr=1;
    for(int i=1;i<n;i++)
    {
        move_inside(i);
        int cnt=press_button();
        if(cnt>=2)
            move_outside(i);
        else
        {
            nr++;
            cul[i]=nr;
            spec.push_back(i);
        }
    }
    for(int i=0;i<n;i++)
        if(cul[i]==0)
            need.push_back({i,0,(int)spec.size()-1});
    for(int i:spec)
        move_outside(i);
    while(!need.empty())
    {
        sort(need.begin(),need.end(),comp);
        vector<date> aux;
        int l=-1;
        int r=-1;
        for(date p:need)
        {
            int who=p.nod;
            int lft=p.l;
            int rgt=p.r;
            int mij=(lft+rgt)/2;
            if(l==-1)
            {
                l=lft;
                r=mij;
                for(int i=l;i<=r;i++)
                    move_inside(spec[i]);
            }
            while(l>lft)
            {
                l--;
                move_inside(spec[l]);
            }
            while(r<mij)
            {
                r++;
                move_inside(spec[r]);
            }
            while(l<lft)
            {
                move_outside(spec[l]);
                l++;
            }
            while(r>mij)
            {
                move_outside(spec[r]);
                r--;
            }
            move_inside(who);
            int cnt=press_button();
            move_outside(who);
            if(cnt>=2)
            {
                int st=l;
                int dr=r;
                if(st!=dr)
                    aux.push_back({who,st,dr});
                else
                    cul[who]=cul[spec[st]];
            }
            else
            {
                int st=mij+1;
                int dr=rgt;
                if(st!=dr)
                    aux.push_back({who,st,dr});
                else
                    cul[who]=cul[spec[st]];
            }
        }
        for(int i=l;i<=r;i++)
            move_outside(spec[i]);
        need=aux;
    }
    for(int i=0;i<n;i++)
    {
        assert(cul[i]>0);
        f[cul[i]]++;
    }
    int minim=1e9;
    for(int i=1;i<=nr;i++)
        minim=min(minim,f[i]);
    return minim;
}

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