Submission #728509

#	Time	Username	Problem	Language	Result	Execution time	Memory
728509		grogu	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	265 ms	652 KiB

insects

        #include "insects.h"
        #define here cerr<<"================================\n"
        #define dbg(x) cerr<<#x<<": "<<x<<endl
        #include <bits/stdc++.h>
        #define ll int
        #define pb push_back
        #define pll pair<ll,ll>
        #define cer(a_) {cerr<<#a_<<": "<<endl; for(ll x_ : a_) cerr<<x_<< " "; cerr<<endl;}
        using namespace std;
        #define maxn 2005
        ll n;
        set<ll> s;
        set<ll> last;
        ll uniq = 0;
        ll F[maxn];
        ll cur = 0;
        void add(ll i){
            if(s.find(i)!=s.end()) return;
            move_inside(i);
            s.insert(i);
        }
        void del(ll i){
            if(s.find(i)==s.end()){
                cerr<<"out"<<endl;
                return;
            }
            move_outside(i);
            s.erase(i);
        }
        ll get(){return press_button();}
        void klir(){
            while(s.size()) del(*s.begin());
            cur = 0;
        }
        ll f(ll x){
            if(F[x]!=-1) return F[x];
            if(cur>x) klir();
            last.clear();
            for(ll x : s) last.insert(x);
            for(ll i = 0;i<n;i++){
                add(i);
                cur = get();
                if(cur>x) del(i);
            }
            return F[x] = s.size();
        }
        ll min_cardinality(ll N) {
            for(ll i = 0;i<maxn;i++) F[i] = -1;
            n = N;
            uniq = f(1);
            klir();
            //dbg(uniq);
            ll rez = 0;
            ll lg = 0,nn = 1;
            while(nn<=n){nn*=2;lg++;}
            for(ll j = lg-1;j>=0;j--){
                //dbg(j);
                if(f(rez+(1<<j))==(rez+(1<<j))*uniq) rez+=(1<<j);
                else{
                    //here;
                    //cer(s);
                    vector<ll> v;
                    for(ll x : s){
                        if(last.find(x)==last.end()){
                            v.pb(x);
                        }
                    }
                    for(ll x : v) del(x);
                    cur = rez;
                }
            }
            return rez;
        }
        /**
        6
        5 8 9 5 9 9
        **/

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