Submission #1191100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191100		Amr	Rarest Insects (IOI22_insects)	C++20	75.90 / 100	32 ms	520 KiB

insects

#include "insects.h"

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
#define fast ios::base_sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll vis[10000];
int min_cardinality(int N) {

    vector<ll> v;
    for(int i = 0; i < N; i++)
    {
        move_inside(i);
        if(press_button()!=1) move_outside(i);
        else v.push_back(i);
    }
    ll cnt = v.sz;
    for(int i = 0; i < v.sz; i++) move_outside(v[i]);
    v.clear();

    //cout << "cnt: " << cnt << endl;

    if(cnt<11)
    {
        set<ll> s;
        for(int i = 0; i< N; i++) s.insert(i);
        ll mn = N;
        for(int times = 0; times < cnt-1; times++)
        {
            auto it = s.begin();
            while(it!=s.end())
            {
                ll x = *it;
                move_inside(x);
                if(press_button()!=v.sz+1) move_outside(x), it++;
                else{
                    v.push_back(x);
                    it = s.erase(it);
                }
            }
            for(int i = 0; i < v.sz; i++) move_outside(v[i]);

            //cout << "cur"<< times << " : " << v.sz << endl;
            mn = min(mn, (ll)v.sz);
            v.clear();
        }
        //cout << s.sz << endl;
        mn = min(mn, (ll)s.sz);
        return mn;
    }
    else
    {
        ll l = 1, r = N/cnt;
        ll mx = -1;
        while(l<r)
        {
            ll mid = r-(r-l)/2;

            ll k = 0;
            if(mid<mx)
            for(int i = N-1; i >= 0; i--)
            {
                if(vis[i]>mid)
                    v.pop_back(), move_outside(i), k =i, vis[i] = 0;
            }

            else
              for(int i = N-1; i >= 0; i--)
            {
                if(vis[i]==mx) v.pop_back(), move_outside(i), k = i,vis[i] = 0;
            }


            for(int i = k; i < N; i++)
            {
                move_inside(i);
                ll press = press_button();
                if(press>mid) move_outside(i),vis[i] = 0;
                else v.push_back(i),vis[i] = press;
            }
            if(cnt * mid == v.sz) l = mid;
            else r = mid-1;

            mx = mid;
            // clear

        }
        return l;
    }

  return 0;
}

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