Submission #1266359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266359		silentloop	Rarest Insects (IOI22_insects)	C++20	53.21 / 100	50 ms	436 KiB

insects

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();
ll n, tam, met;
const int MAXN=2001;
bool ins[MAXN];
bool can(ll x)
{
    ll i, cant=met;
    vector<bool>ag(n);
    for(i=0; i<n; i++)
    {
        if(ins[i])
            continue;
        move_inside(i);
        if(press_button()>x)
            move_outside(i);
        else
        {
            ag[i]=1;
            cant++;
        }
    }
    bool ans=0;
    if(cant==tam*x)
    {
        for(i=0; i<n; i++)
            ins[i]=ins[i]|ag[i];
        met=cant;
        return 1;
    }
    for(i=0; i<n; i++)
    {
        if(ag[i])
            move_outside(i);
    }
    return 0;
}

int min_cardinality(int N)
{
    ll i;
    n=N;
    vector<ll>v;
    move_inside(0);
    v.pb(0);
    ins[0]=1;
    for(i=1; i<n; i++)
    {
        move_inside(i);
        if(press_button()==1)
        {
            v.pb(i);
            ins[i]=1;
        }
        else
            move_outside(i);
    }
    tam=sz(v);
    if(tam==1)
        return N;
    else if(tam==2)
    {
        for(i=0; i<n; i++)
        {
            if(ins[i]==1)
                continue;
            move_inside(i);
        }
        return N-press_button();
    }
    met=tam;
    ll l=2, r=n/tam, piv, pos=1;

    while(l<=r)
    {
        piv=(l+r)/2;
        if(can(piv))
        {
            l=piv+1;
            pos=piv;
        }
        else
            r=piv-1;
    }
    return int(pos);
}

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