Submission #1072559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072559		Unforgettablepl	Rarest Insects (IOI22_insects)	C++17	96.07 / 100	54 ms	856 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<int> last_removed;
    vector<bool> currently(N);
    vector<bool> skipped(N);
    auto check = [&](int x) {
        last_added.clear();
        last_removed.clear();
        int curr = 0;
        for(int i=0;i<N;i++)if(currently[i])curr++;
        for(int i=0;i<N;i++) {
            if(currently[i])continue;
            if(skipped[i])continue;
            currently[i]=true;
            move_inside(i);
            if(press_button()<=x) {
                last_added.emplace_back(i);
                if(++curr==uniques*x)return true;
                continue;
            }
            last_removed.emplace_back(i);
            move_outside(i);
            currently[i]=false;
        }
        return curr==uniques*x;
    };
    auto revert = [&]() {
        for(int&i:last_added) {
            currently[i]=false;
            move_outside(i);
        }
        for(int&i:last_removed)skipped[i]=true;
    };
    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: 71.07 / 75