Submission #812803

#	Time	Username	Problem	Language	Result	Execution time	Memory
812803		andrei_boaca	Rarest Insects (IOI22_insects)	C++17	57.43 / 100	105 ms	672 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef pair<int,int> pii;
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;
}
struct ev
{
    int l,r,nod,poz;
};
bool compev(ev a, ev b)
{
    return a.l<b.l;
}
int f[2005];
ev v[2005][3];
int have[2005][3];
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);
        }
    }
    if(spec.size()==1)
        return n;
    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())
    {
        vector<ev> events;
        for(date p:need)
        {
            int nod=p.nod;
            int l=p.l;
            int r=p.r;
            have[nod][0]=0;
            have[nod][1]=0;
            have[nod][2]=0;
            if(r-l+1==2)
            {
                ev a={l,l,nod,0};
                ev b={r,r,nod,1};
                events.push_back(a);
                v[nod][0]=a;
                v[nod][1]=b;
                v[nod][2]={-1,-1,0,0};
            }
            else
            {
                int lg=r-l+1;
                int mij1=l+lg/3-1;
                int mij2=mij1+lg/3;
                //assert(l<=mij1&&mij1+1<=mij2&&mij2+1<=r);
                ev a={l,mij1,nod,0};
                ev b={mij1+1,mij2,nod,1};
                ev c={mij2+1,r,nod,2};
                v[nod][0]=a;
                v[nod][1]=b;
                v[nod][2]=c;
                events.push_back(a);
                events.push_back(b);
            }
        }
        sort(events.begin(),events.end(),compev);
        int l=-1;
        int r=-1;
        for(auto p:events)
        {
            int nod=p.nod;
            int lft=p.l;
            int rgt=p.r;
            if(have[nod][0]+have[nod][1]+have[nod][2]>=1)
                continue;
            if(l==-1)
            {
                l=lft;
                r=rgt;
                for(int i=lft;i<=rgt;i++)
                    move_inside(spec[i]);
            }
            if(lft>r)
            {
                for(int i=l;i<=r;i++)
                    move_outside(spec[i]);
                l=lft;
                r=rgt;
                for(int i=l;i<=r;i++)
                    move_inside(spec[i]);
            }
            move_inside(nod);
            int cnt=press_button();
            move_outside(nod);
            if(cnt>=2)
                have[nod][p.poz]=1;
        }
        for(int i=l;i<=r;i++)
            move_outside(spec[i]);
        vector<date> aux;
        for(date p:need)
        {
            int nod=p.nod;
            int l=-1,r=-1;
            for(int z=0;z<=2;z++)
                if(have[nod][z])
                {
                    l=v[nod][z].l;
                    r=v[nod][z].r;
                }
            if(l==-1)
            {
                if(v[nod][2].l==-1)
                {
                    l=v[nod][1].l;
                    r=v[nod][1].r;
                }
                else
                {
                    l=v[nod][2].l;
                    r=v[nod][2].r;
                }
            }
            if(l==r)
                cul[nod]=cul[spec[l]];
            else
                aux.push_back({nod,l,r});
        }
        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: 15 / 15
• Subtask 3: 32.43 / 75