#include <iostream>
#include <random>
#include <algorithm>
#include <iomanip>
template<typename T>
struct cmp_count
{
static unsigned int n;
bool operator()(const T& lhs, const T& rhs)
{
++n;
static std::less<T> less;
return less(lhs,rhs);
}
unsigned int count() const { return n; }
void reset() { n = 0; }
};
template<typename T>
unsigned int cmp_count<T>::n = 0;
int main()
{
std::random_device rd;
std::mt19937 rng(rd());
for (int i=1024; i<100*1024; i += 1024)
{
std::vector<int> arr;
arr.reserve(i);
std::generate_n(std::back_inserter(arr), arr.capacity(), rng);
cmp_count<int> cmp;
std::make_heap(arr.begin(), arr.end(), cmp);
// report output and reset
std::cout << std::setw(12) << i;
std::cout << std::setw(12) << static_cast<unsigned int>(std::round(std::log2(i)*i));
std::cout << std::setw(12) << 3*arr.size();
std::cout << std::setw(12) << cmp.count() << '\n';
cmp.reset();
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aW9tYW5pcD4KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CnN0cnVjdCBjbXBfY291bnQKewogICAgc3RhdGljIHVuc2lnbmVkIGludCBuOwogICAgCiAgICBib29sIG9wZXJhdG9yKCkoY29uc3QgVCYgbGhzLCBjb25zdCBUJiByaHMpCiAgICB7CiAgICAgICAgKytuOwogICAgICAgIHN0YXRpYyBzdGQ6Omxlc3M8VD4gbGVzczsKICAgICAgICByZXR1cm4gbGVzcyhsaHMscmhzKTsKICAgIH0KICAgIAogICAgdW5zaWduZWQgaW50IGNvdW50KCkgY29uc3QgeyByZXR1cm4gbjsgfQogICAgdm9pZCByZXNldCgpIHsgbiA9IDA7IH0KfTsKCnRlbXBsYXRlPHR5cGVuYW1lIFQ+CnVuc2lnbmVkIGludCBjbXBfY291bnQ8VD46Om4gPSAwOwoKaW50IG1haW4oKQp7CiAgICBzdGQ6OnJhbmRvbV9kZXZpY2UgcmQ7CiAgICBzdGQ6Om10MTk5Mzcgcm5nKHJkKCkpOwoKICAgIGZvciAoaW50IGk9MTAyNDsgaTwxMDAqMTAyNDsgaSArPSAxMDI0KQogICAgewogICAgICAgIHN0ZDo6dmVjdG9yPGludD4gYXJyOwogICAgICAgIGFyci5yZXNlcnZlKGkpOwogICAgICAgIHN0ZDo6Z2VuZXJhdGVfbihzdGQ6OmJhY2tfaW5zZXJ0ZXIoYXJyKSwgYXJyLmNhcGFjaXR5KCksIHJuZyk7CiAgICAgICAgCiAgICAgICAgY21wX2NvdW50PGludD4gY21wOwogICAgICAgIHN0ZDo6bWFrZV9oZWFwKGFyci5iZWdpbigpLCBhcnIuZW5kKCksIGNtcCk7CiAgICAgICAgCiAgICAgICAgLy8gcmVwb3J0IG91dHB1dCBhbmQgcmVzZXQKICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KDEyKSA8PCBpOwogICAgICAgIHN0ZDo6Y291dCA8PCBzdGQ6OnNldHcoMTIpIDw8IHN0YXRpY19jYXN0PHVuc2lnbmVkIGludD4oc3RkOjpyb3VuZChzdGQ6OmxvZzIoaSkqaSkpOwogICAgICAgIHN0ZDo6Y291dCA8PCBzdGQ6OnNldHcoMTIpIDw8IDMqYXJyLnNpemUoKTsKICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KDEyKSA8PCBjbXAuY291bnQoKSA8PCAnXG4nOwogICAgICAgIGNtcC5yZXNldCgpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=