Submission #819224

#	Time	Username	Problem	Language	Result	Execution time	Memory
819224		andrei_boaca	Rarest Insects (IOI22_insects)	C++17	10 / 100	19 ms	316 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 p=0;p<n;p++)
        if(cul[p]!=0)
        {
            int pmax=p;
            for(int i=p+1;i<n&&cul[i]==0;i++)
            {
                pmax=max(pmax,i);
                int lft=0;
                int rgt=cul[p]-1;
                if(lft==rgt)
                    cul[i]=cul[p];
                else
                    need.push_back({i,lft,rgt});
            }
            p=pmax;
            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]);
                    }
                    if(lft>r)
                    {
                      for(int i=l;i<=r;i++)
                        move_outside(spec[i]);
                      l=lft;
                      r=mij;
                      for(int i=l;i<=r;i++)
                        move_inside(spec[i]);
                    }
                    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;
                sort(need.begin(),need.end(),comp);
            }
        }
    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: 0 / 15
• Subtask 3: 0 / 75