#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <unistd.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <vector>
#include <ctime>
#include <math.h>
#include <fstream>
#include <iterator>
#include <math.h>
#include <set>
#include <sstream>
#include <unordered_set>



double c =  1000;
double eps = 0.1;


namespace hash {
    inline uint64_t rotl64(uint64_t x, int8_t r) {
        return (x << r) | (x >> (64 - r));
    }

    inline uint64_t fmix64(uint64_t k) {
        k ^= k >> 33;
        k *= 0xff51afd7ed558ccdull;
        k ^= k >> 33;
        k *= 0xc4ceb9fe1a85ec53ull;
        k ^= k >> 33;
        return k;
    }

    class murmurhash3 {
    public:
        size_t seed;
        murmurhash3(size_t seed = 0) : seed(seed) {}

        template<typename T>
        uint64_t operator()(const T &x) const {
            return operator()(&x, sizeof(x));
        }

        uint64_t operator()(const void *key, const size_t len) const {
            uint64_t h1 = seed;
            uint64_t h2 = seed;
            const uint64_t c1 = 0x87c37b91114253d5ull;
            const uint64_t c2 = 0x4cf5ad432745937full;
            const uint64_t *blocks = (const uint64_t *) key;
            const size_t nblocks = len / 16;
            for (size_t i = 0; i < nblocks; i++) {
                h1 = (rotl64(h1 ^ (rotl64(*blocks++ * c1, 31) * c2), 27) + h2) * 5 + 0x52dce729ul;
                h2 = (rotl64(h2 ^ (rotl64(*blocks++ * c2, 33) * c1), 31) + h1) * 5 + 0x38495ab5ul;
            }

            const uint8_t *tail = (const uint8_t *) blocks;
            uint64_t k1 = 0;
            uint64_t k2 = 0;
            switch (len & 15) {
                case 15:
                    k2 ^= ((uint64_t) tail[14]) << 48;
                case 14:
                    k2 ^= ((uint64_t) tail[13]) << 40;
                case 13:
                    k2 ^= ((uint64_t) tail[12]) << 32;
                case 12:
                    k2 ^= ((uint64_t) tail[11]) << 24;
                case 11:
                    k2 ^= ((uint64_t) tail[10]) << 16;
                case 10:
                    k2 ^= ((uint64_t) tail[9]) << 8;
                case 9:
                    k2 ^= ((uint64_t) tail[8]) << 0;
                    h2 ^= rotl64(k2 * c2, 33) * c1;
                case 8:
                    k1 ^= ((uint64_t) tail[7]) << 56;
                case 7:
                    k1 ^= ((uint64_t) tail[6]) << 48;
                case 6:
                    k1 ^= ((uint64_t) tail[5]) << 40;
                case 5:
                    k1 ^= ((uint64_t) tail[4]) << 32;
                case 4:
                    k1 ^= ((uint64_t) tail[3]) << 24;
                case 3:
                    k1 ^= ((uint64_t) tail[2]) << 16;
                case 2:
                    k1 ^= ((uint64_t) tail[1]) << 8;
                case 1:
                    k1 ^= ((uint64_t) tail[0]) << 0;
                    h1 ^= rotl64(k1 * c1, 31) * c2;
            };

            h1 ^= len;
            h2 ^= len;
            h1 += h2;
            h2 += h1;
            h1 = fmix64(h1);
            h2 = fmix64(h2);
            h1 += h2;
            h2 += h1;
            return h2;
        }


    };


}




struct Bjkst {
    uint64_t z;
    std::unordered_set<uint64_t> B;
    uint64_t curr_approx;
    hash::murmurhash3 hash;


};


void bjkst(Bjkst &curr, uint64_t &elem) {
    //if (p(hash_combine(curr.seed, elem)) >= curr.z) {
    uint64_t curr_hash = curr.hash(elem);

    if (!((curr_hash)& ((1ull << curr.z) - 1))) {
        curr.B.insert(curr_hash);
        while (curr.B.size() >= (c / (eps*eps))) {
            curr.z++;
            for (auto it = curr.B.begin(); it != curr.B.end(); it++) {
                if (*it & ((1ull << curr.z) - 1)) {
                    curr.B.erase(it);
                } else
                    curr.z++;
            }
        }
    }
    curr.curr_approx = curr.B.size() << curr.z;
}



double CalcMHWScore(std::vector<Bjkst> &vec)
{
    double median;
    size_t size = vec.size();

    std::sort(vec.begin(), vec.end(),
              [](const Bjkst a, const Bjkst b) {
                  return a.curr_approx < b.curr_approx;
              });

    if (size  % 2 == 0)
    {
        median = (vec[size / 2 - 1].curr_approx + vec[size / 2].curr_approx) / 2;
    }
    else
    {
        median = vec[size / 2].curr_approx;
    }

    return median;
}


int main(int argc, char** argv) {

    srand (time(NULL));

    int m = log(eps)*(-1);
    std::vector<Bjkst> vec;
    std::set<uint64_t> a;
    for (int i = 0;  i < m; ++i) {
        Bjkst curr;
        curr.z = 0;
        curr.hash.seed = i;
        vec.push_back(curr);
    }
    for(int i =0; i < 10000000; ++i) {
        uint64_t elem;
        uint64_t rand1 =rand() % 10000000 + 1;
        elem = i % rand1;
        a.insert(elem);
        for (int i = 0;  i < m; ++i) {
            bjkst(vec[i], elem);
        }
    }
    std::cout << vec[0].B.size() << std::endl;
    std::cout << CalcMHWScore(vec) << std::endl;
    std::cout << a.size() << std::endl;


}


/*

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Usage: ./" << argv[0] << " {precision}]" << std::endl;
        return 1;
    }

    {
        std::string precisionStr(argv[1]);
        std::istringstream is(precisionStr);
        is >> eps;
    }
    int m = log(eps)*(-1);


    std::vector<Bjkst> vec;
    for (int i = 0;  i < m; ++i) {
        Bjkst curr;
        curr.z = 0;
        curr.seed = i*(i+1)+11;
        vec.push_back(curr);
    }

    while (!(std::cin >> std::ws).eof()) {
        size_t elem;
        std::cin >> elem;
        for (int i = 0;  i < m; ++i) {
            bjkst(vec[i],elem);
        }
    }


    std::cout << CalcMHWScore(vec);

}
*/