#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()
{
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(),
[](){ static int i=0; return ++i;});
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+CnVuc2lnbmVkIGludCBjbXBfY291bnQ8VD46Om4gPSAwOwoKaW50IG1haW4oKQp7CiAgICBmb3IgKGludCBpPTEwMjQ7IGk8MTAwKjEwMjQ7IGkgKz0gMTAyNCkKICAgIHsKICAgICAgICBzdGQ6OnZlY3RvcjxpbnQ+IGFycjsKICAgICAgICBhcnIucmVzZXJ2ZShpKTsKICAgICAgICBzdGQ6OmdlbmVyYXRlX24oc3RkOjpiYWNrX2luc2VydGVyKGFyciksIGFyci5jYXBhY2l0eSgpLAogICAgICAgICAgICAgICAgICAgIFtdKCl7IHN0YXRpYyBpbnQgaT0wOyByZXR1cm4gKytpO30pOwogICAgICAgIAogICAgICAgIGNtcF9jb3VudDxpbnQ+IGNtcDsKICAgICAgICBzdGQ6Om1ha2VfaGVhcChhcnIuYmVnaW4oKSwgYXJyLmVuZCgpLCBjbXApOwogICAgICAgIAogICAgICAgIC8vIHJlcG9ydCBvdXRwdXQgYW5kIHJlc2V0CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dygxMikgPDwgaTsKICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KDEyKSA8PCBzdGF0aWNfY2FzdDx1bnNpZ25lZCBpbnQ+KHN0ZDo6cm91bmQoc3RkOjpsb2cyKGkpKmkpKTsKICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KDEyKSA8PCAzKmFyci5zaXplKCk7CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dygxMikgPDwgY21wLmNvdW50KCkgPDwgJ1xuJzsKICAgICAgICBjbXAucmVzZXQoKTsKICAgIH0KICAgIHJldHVybiAwOwp9