Submission #1235885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235885		Muhammad_Aneeq	Rarest Insects (IOI22_insects)	C++17	100 / 100	15 ms	444 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

int const sz=2000;
bitset<sz>ind,ind1,ver[sz];
int pre;
bool chn;
int ask()
{
    if (chn==0)
        return pre;
    pre=press_button();
    chn=0;
    return pre;
}
// int ran(int j)
// {
//     return rand()%j;
// }
int min_cardinality(int N) 
{
    srand(time(0));
    int colors=0;
    vector<int>inds;
    for (int i=0;i<N;i++)
        inds.push_back(i);
    mt19937 mt(783242309);
    shuffle(inds.begin(),inds.end(),mt);
    for (int i=0;i<N;i++)
    {
        ind[inds[i]]=1;
        chn=1;
        move_inside(inds[i]);
        colors++;
        if (ask()>1)
        {
            ind[inds[i]]=0;
            chn=1;
            move_outside(inds[i]);
            colors--;
        }
    }
    ver[1]=ind;
    set<int>s;
    s.insert(1);
    for (int i=0;i<N;i++)
        ind1[i]=1-ind[i];
    int cnt=colors;
    int st=1,en=N/colors+1;
    while (st+1<en)
    {
        int mid=(st+en)/2;
        auto z=s.lower_bound(mid);
        z--;
        int pre=*z;
        for (int i=0;i<N;i++)
        {
            if (ver[pre][inds[i]]==ind[inds[i]]) continue;
            if (ver[pre][inds[i]])
            {
                chn=1;
                move_inside(inds[i]);
                ind[inds[i]]=1;
                ind1[inds[i]]=0;
                cnt++;
            }   
            else
            {
                chn=1;
                move_outside(inds[i]);
                ind[inds[i]]=0;
                ind1[inds[i]]=1;
                cnt--;
            }
        }
        for (int i=0;i<N;i++)
        {
            if (cnt==colors*mid)
                break;
            if (ind1[inds[i]])
            {
                chn=1;
                move_inside(inds[i]);
                ind[inds[i]]=1;
                cnt++;
                if (ask()>mid)
                {
                    cnt--;
                    chn=1;
                    move_outside(inds[i]);
                    ind[inds[i]]=0;
                }
            }
        }
        if (cnt==colors*mid)
        {
            st=mid;
            if (st+1>=en)
                break;
            for (int i=0;i<N;i++)
            {
                if (ind[inds[i]])
                    ind1[inds[i]]=0;
            }
        }
        else
        {
            en=mid;
            if (st+1>=en)
                break;
            for (int i=0;i<N;i++)
            {
                if (ind[inds[i]])
                    continue;
                else
                    ind1[inds[i]]=0;
            }
        }
        s.insert(mid);
        ver[mid]=ind;
    }
    return st;
}

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