Submission #726127

#	Time	Username	Problem	Language	Result	Execution time	Memory
726127		TheSahib	Rarest Insects (IOI22_insects)	C++17	99.77 / 100	66 ms	464 KiB

insects

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

using namespace std;


int min_cardinality(int N) {
    vector<int> types;
    vector<int> left;
    for (int i = 0; i < N; i++)
    {
        move_inside(i);
        if(press_button() > 1){
            left.push_back(i);
            move_outside(i);
        }
        else{
            types.push_back(i);
        }
    }
    if(types.size() == 1) return N;
    int l = 2, r = N / types.size() + 1;
    int ans = 1;
    int leftOutN = 0;
    while(l <= r){
        vector<int> tmp;
        int mid = (l + r) / 2;

        for(int a:left){
            move_inside(a);
            if(press_button() > mid){
                move_outside(a);
                tmp.push_back(a);
            }
        }

        if(N - tmp.size() - leftOutN == mid * types.size()){
            l = mid + 1;
            ans = mid;
            left = tmp;
        }
        else{
            r = mid - 1;
            vector<int> tmp1;
            for(int a:left){
                if(find(tmp.begin(), tmp.end(), a) == tmp.end()){
                    move_outside(a);
                    tmp1.push_back(a);
                }
                else{
                    ++leftOutN;
                }
            }
            left = tmp1;
        }
    }
    return ans;
}

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