Submission #728701

#	Time	Username	Problem	Language	Result	Execution time	Memory
728701		grogu	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	274 ms	712 KiB

insects

    #include "insects.h"
    #define dbg(x) cerr<<#x<<": "<<x<<endl
    #include <bits/stdc++.h>
    #define ll int
    #define pll pair<ll,ll>
     
    using namespace std;
    #define maxn 2005
    ll n;
    set<ll> s;
    ll uniq = 0;
    ll a[maxn];
    ll F[maxn];
    bool ok[maxn];
    ll val[maxn];
    ll cur = 0;
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    void add(ll i){
        if(s.find(i)!=s.end()) return;
        move_inside(a[i]);
        s.insert(i);
    }
    void del(ll i){
        if(s.find(i)==s.end()){
            cerr<<"out"<<endl;
            return;
        }
        move_outside(a[i]);
        s.erase(i);
    }
    ll get(){return press_button();}
    void klir(){
        while(s.size()) del(*s.begin());
    }
    set<ll> newe;
    ll f(ll x){
        if(F[x]!=-1) return F[x];
        newe.clear();
        for(ll i = 0;i<n;i++){
            add(i);
            cur = get();
            if(cur>x) del(i);
            else newe.insert(i);
        }
        return F[x] = s.size();
    }
    ll min_cardinality(ll N) {
        for(ll i = 0;i<maxn;i++) F[i] = -1;
        n = N;
        for(ll i = 0;i<n;i++) a[i] = i;
        shuffle(a,a+n,rng);
        for(ll i = 0;i<n;i++) ok[i] = 1;
        uniq = f(1);
        //dbg(uniq);
        ll l = 2, r = n,mid,rez = 1;
        while(l<=r){
            mid = (l+r)/2;
            if(f(mid)==uniq*mid) l = mid+1,rez = mid;
            else{
                for(ll x : newe) del(x);
                cur = rez;
                r = mid-1;
            }
        }
        return rez;
    }
    /**
    6
    5 8 9 5 9 9
    **/

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