Submission #1235596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235596		Muhammad_Aneeq	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	396 KiB

insects

#include "insects.h"
#include <vector>
#include <bitset>
#include <map>
#include <set>
using namespace std;
int const sz=2010;
vector<bool>ind(sz,0);
map<vector<bool>,bool>seen;
int ask()
{
    if (seen.find(ind)==seen.end())
        seen[ind]=press_button();
    return seen[ind];
}
int min_cardinality(int N) 
{
    int colors=0;
    for (int i=0;i<N;i++)
    {
        ind[i]=1;
        move_inside(i);
        colors++;
        if (ask()>1)
        {
            ind[i]=0;
            move_outside(i);
            colors--;
        }
    }
    int cnt=colors;
    int st=1,en=N/colors+1;
    while (st+1<en)
    {
        set<int>rem;
        int mid=(st+en)/2;
        for (int i=N-1;i>=0;i--)
        {
            if (ask()<=mid)
                break;
            if (ind[i]==0)
                continue;
            int z=ask();
            ind[i]=0;
            move_outside(i);
            int y=ask();
            cnt--;
            if (z!=y)
                rem.insert(i);
        }
        for (int i=0;i<N;i++)
        {
            if (cnt==colors*mid)
                break;
            if (ind[i]==0&&rem.find(i)==rem.end())
            {
                ind[i]=1;
                cnt++;
                move_inside(i);
                if (ask()>mid)
                {
                    move_outside(i);
                    cnt--;
                    ind[i]=0;
                }
            }
        }
        if (cnt==colors*mid)
            st=mid;
        else
            en=mid;
    }
    return st;
}

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