Submission #1072550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072550		Unforgettablepl	Rarest Insects (IOI22_insects)	C++17	50 / 100	128 ms	688 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int min_cardinality(int N){
    int uniques = 1;
    move_inside(0);
    vector uni = {0};
    for(int i=1;i<N;i++) {
        move_inside(i);
        if(press_button()==1){ uniques++;uni.emplace_back(i);}
        else move_outside(i);
    }
    for(int&i:uni)move_outside(i);
    vector<int> last_added;
    vector<bool> currently(N);
    auto check = [&](int x) {
        last_added.clear();
        for(int i=0;i<N;i++) {
            if(currently[i])continue;
            currently[i]=true;
            move_inside(i);
            if(press_button()<=x) {
                last_added.emplace_back(i);
                continue;
            }
            move_outside(i);
            currently[i]=false;
        }
        int curr = 0;
        for(int i=0;i<N;i++)if(currently[i])curr++;
        return curr>=uniques*x;
    };
    auto revert = [&]() {
        for(int&i:last_added) {
            currently[i]=false;
            move_outside(i);
        }
    };
    int ans = 0;
    for(int jump=1024;jump;jump/=2) {
        if(ans+jump>N/uniques)continue;
        if(check(ans+jump))ans+=jump;
        else revert();
    }
    return ans;
}

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