Submission #631152

#	Time	Username	Problem	Language	Result	Execution time	Memory
631152		il9	Rarest Insects (IOI22_insects)	C++17	61.54 / 100	134 ms	412 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int n)
{
    for(int i =0;i<n;i++)
    {
        move_inside(i);

    }
     int high=press_button()+1;
    for(int i=0;i<n;i++) move_outside(i);
    int low=2;

    int mid;
    bool inside[n];
    for(int i=0;i<n;i++)
    {
        inside[i]=0;
    }
    int types=0;
    for(int i=0;i<n;i++)
    {
        move_inside(i);
        if(press_button()==1)
        {
            types++;
        }else
        {
            move_outside(i);
        }


    }
        for(int i=0;i<n;i++)
    {

            move_outside(i);

    }
    int pos[n];
    for(int i=0;i<n;i++)
    {
        pos[i]=high+4;

    }
    int added=0;
    while(low<high)
    {
        mid=low+(high-low)/5;

        for(int i=0;i<n;i++)
        {
            if(!inside[i])
            {

                if(mid<=pos[i])
                {


                    move_inside(i);
                    inside[i]=1;
                    int tp=press_button();
                    added++;
                    if(tp>mid)
                    {
                        inside[i]=0;
                        added--;
                        move_outside(i);
                      //  pos[i]=mid-1;
                    }
                }
            }


        }
        if(types*mid==added)
        {
            low=mid+1;
        }else
        {

            high=mid;
            added=0;
            for(int i=0;i<n;i++)
            {
                if(inside[i])
                {
                    move_outside(i);
                }
                inside[i]=0;

            }
        }


    }
    return high-1;


}

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