Submission #755120

#	Time	Username	Problem	Language	Result	Execution time	Memory
755120		Rafi22	Rarest Insects (IOI22_insects)	C++17	0 / 100	258 ms	9596 KiB

insects

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

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

int ans=1,m;

void rek(vector<int>a)
{
    if(sz(a)<m) return ;
    int k=(sz(a)/m+1)/2;
    vector<int>T,N;
    bool is=0;
    for(auto x:a)
    {
        move_inside(x);
        int c=press_button();
        if(c>=k) is=1;
        if(c>k)
        {
            move_outside(x);
            N.pb(x);
        }
        else T.pb(x);
    }
    for(auto x:T) move_outside(x);
    if(is)
    {
        ans+=k;
        rek(N);
    }
    else rek(T);
}

int min_cardinality(int n)
{
    vector<int>V;
    for(int i=0;i<n;i++)
    {
        move_inside(i);
        if(press_button()>1)
        {
            move_outside(i);
            V.pb(i);
        }
        else m++;
    }
    rek(V);
    return ans;
}

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