Submission #837854

#	Time	Username	Problem	Language	Result	Execution time	Memory
837854		fatemetmhr	Rarest Insects (IOI22_insects)	C++17	60.77 / 100	112 ms	896 KiB

insects

        // Be name khoda //
         
        #include "insects.h"
        #include <bits/stdc++.h>
         
        using namespace std;
         
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
         
        #define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
        #define all(x)   x.begin(), x.end()
        #define pb       push_back
        #define mp       make_pair
        #define fi       first
        #define se       second
         
        typedef long long ll;
         
        const int mod   = 1e9 + 9;
        const int maxn5 = 1e5 + 10;
         
        int dif, n, pw[maxn5], per[maxn5], hsh = 0;
        bool mark[maxn5];
        vector <int> av;
        map <int, int> asked;
        int c[3];
         
         
        void fix(int &a){
            if(a < 0)
                a += mod;
            if(a >= mod)
                a -= mod;
        }
         
        void mmove_outside(int x){
            x = per[x];
            move_outside(x);
            fix(hsh -= pw[x]);
            c[0]++;
        }
         
        void mmove_inside(int x){
            x = per[x];
            move_inside(x);
            fix(hsh += pw[x]);
            c[1]++;
        }
         
        int ppress_button(){
            if(asked.find(hsh) == asked.end())
                asked[hsh] = press_button();
            c[2]++;
            return asked[hsh];
        }
         
        int find_all_same(int id){
            mark[id] = true;
            mmove_inside(id);
            int cnt = 1;
            for(int i = 0; i < n; i++) if(!mark[i]){
                mmove_inside(i);
                if(ppress_button() == 2){
                    mark[i] = true;
                    cnt++;
                }
                mmove_outside(i);
            }
            mmove_outside(id);
            return cnt;
        }
         
        int count_dif(){
            av.clear();
            hsh = 0;
            for(int i = 0; i < n; i++){
                mmove_inside(i);
                av.pb(i);
                if(ppress_button() == 2){
                    mmove_outside(i);
                    av.pop_back();
                }
            }
            for(auto u : av)
                mmove_outside(u);
            return av.size();
        }
         
        bool check(int x){
            av.clear();
            hsh = 0;
            for(int i = 0; i < n; i++){
                av.pb(i);
                mmove_inside(i);
                if(i + 1 > x && ppress_button() > x){
                    mmove_outside(i);
                    av.pop_back();
                }
                if(int(av.size()) == x * dif)
                    break;
                if(int(av.size()) + n - i - 1 < x * dif)
                    break;
            }
            for(auto u : av)
                mmove_outside(u);
            return int(av.size()) == x * dif;
        }
         
        int min_cardinality(int N) {
            n = N;
            pw[0] = 1;
            for(int i = 0; i < n; i++){
                per[i] = i;
                if(i)
                    pw[i] = pw[i - 1] * 7ll % mod;
            }
            //shuffle(per, per + n, rng);
            dif = count_dif();
            if(dif == 1)
                return n;
            if(dif <= 8){
                int mn = n;
                for(int i = 0; i < n; i++) if(!mark[i]){
                    mn = min(mn, find_all_same(i));
                    if(mn == 1)
                        return 1;
                }
                return mn;
            }
            int lo = 1, hi = n / dif + 1;
            while(hi - lo > 1){
                int mid = (lo + hi) >> 1;
                if(check(mid))
                    lo = mid;
                else
                    hi = mid;
            }
            return lo;
        }

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