Submission #1072560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072560		Unforgettablepl	Rarest Insects (IOI22_insects)	C++17	99.83 / 100	44 ms	848 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;
    int L = 1;
    int R = N/uniques;
    while(L<=R) {
        int mid = (L+R)/2;
        if(check(mid)) {
            ans=mid;
            L = mid+1;
        } else {
            revert();
            R = mid-1;
        }
    }
    return ans;
}

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