Submission #728690

#	Time	Username	Problem	Language	Result	Execution time	Memory
728690		grogu	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	205 ms	484 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());
    }
    ll f(ll x){
        if(F[x]!=-1) return F[x];
        if(cur>x){
            for(ll i = n-1;i>=0;i--){
                if(s.find(i)!=s.end()&&val[i]>x) del(i);
            }
        }
        for(ll i = 0;i<n;i++){
            add(i);
            cur = get();
            if(cur>x) del(i);
            else val[i] = cur;
        }
        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 = 1, r = n/uniq,mid,rez = n;
        while(l<=r){
            mid = (l+r)/2;
            if(f(mid)==uniq*mid) l = mid+1,rez = mid;
            else{
                for(ll i = 0;i<n;i++){
                    if(s.find(i)!=s.end()&&val[i]>=mid) ok[i] = 0;
                }
                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