제출 #1191074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191074		Amr	Rarest Insects (IOI22_insects)	C++20	57.14 / 100	45 ms	448 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);

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<9)
    {
        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;
        while(l<r)
        {
            ll mid = r-(r-l)/2;
            for(int i = 0; i < N; i++)
            {
                move_inside(i);
                if(press_button()>mid) move_outside(i);
                else v.push_back(i);
            }
            if(cnt * mid == v.sz) l = mid;
            else r = mid-1;

            // clear
            for(int i = 0; i < v.sz; i++) move_outside(v[i]);
            v.clear();
        }
        return l;
    }

  return 0;
}

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