Submission #650082

#	Time	Username	Problem	Language	Result	Execution time	Memory
650082		huutuan	Rarest Insects (IOI22_insects)	C++17	100 / 100	74 ms	1316 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>
 
using namespace std;
 
int min_cardinality(int n){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> sus(n); iota(sus.begin(), sus.end(), 0); shuffle(sus.begin(), sus.end(), rng);
    set<int> s;
    auto in=[&](int i){
        if (s.count(i)) return;
        s.insert(i);
        move_inside(sus[i]);
    };
    auto out=[&](int i){
        if (!s.count(i)) return;
        s.erase(i);
        move_outside(sus[i]);
    };
    for (int i=0; i<n; ++i){
        in(i);
        if (press_button()>1) out(i);
    }
    int cnt=s.size();
    map<int, set<int>> memo;
    memo[1]=s;
    for (int i=0; i<n; ++i) memo[n].insert(i);
    int l=2, r=n/cnt;
    while (l<=r){
        int mid=(l+r)>>1;
        auto it=memo.lower_bound(mid);
        set<int> t;
        for (int i:it->second) if (!s.count(i)){
            in(i);
            if (press_button()>mid) out(i);
            else t.insert(i);
            if ((int)s.size()>=cnt*mid) break;
        }
        int k=s.size();
        memo[mid]=s;
        if (k>=cnt*mid) l=mid+1;
        else{
            r=mid-1;
            for (int i:t) out(i);
        }
    }
    return r;
}

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