#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <utility>
#include <string>
#include <vector>
#include <memory>
#include <limits>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
 
typedef long long ll;
 
struct document
{
    float rank;
    document(float rank):
        rank(rank)
    { }
};
 
using doc_ptr = shared_ptr<document>;
 
bool operator < (const doc_ptr& x, const doc_ptr& y)
{
    return x->rank < y->rank;
}
 
int main()
{
    int n = 10;
    auto cmp_by_rank = [](const doc_ptr& x, const doc_ptr& y) { return x->rank < y->rank; };
    auto cmp_by_ptr = [](const doc_ptr& x, const doc_ptr& y) { return x.get() < y.get(); };
 
    vector<doc_ptr> v;
 
    for(int i = 0; i < n; i++) {
        float r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
        v.emplace_back(make_shared<document>(r));
    }
 
    sort(v.begin(), v.end());
 
    for(const auto& doc: v)
        cout << doc->rank << " " << uint64_t(doc.get()) << endl;
 
    cout << "v is sorted = " << std::is_sorted(v.begin(), v.end()) << endl;
    cout << "v is sorted (by rank): " << is_sorted(v.begin(), v.end(), cmp_by_rank) << endl;
    cout << "v is sorted (by ptr): " << is_sorted(v.begin(), v.end(), cmp_by_ptr) << endl;
    cout << "----" << endl;
 
    priority_queue<doc_ptr> pq;
    for(int i = 0; i < n; i++) {
        float r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
        pq.push(make_shared<document>(r));
    }
 
    vector<doc_ptr> pq_v;
 
    while(!pq.empty()) {
        cout << pq.top()->rank << " " << uint64_t(pq.top().get()) << endl;
        pq_v.push_back(pq.top());
        pq.pop();
    }
 
    cout << "pq_v is sorted: " << is_sorted(pq_v.rbegin(), pq_v.rend()) << endl;
    cout << "pq_v is sorted (by rank): " << is_sorted(pq_v.rbegin(), pq_v.rend(), cmp_by_rank) << endl;
    cout << "pq_v is sorted (by ptr): " << is_sorted(pq_v.rbegin(), pq_v.rend(), cmp_by_ptr) << endl;
 
    return 0;
}
 

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPG1lbW9yeT4KI2luY2x1ZGUgPGxpbWl0cz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CgpzdHJ1Y3QgZG9jdW1lbnQKewogICAgZmxvYXQgcmFuazsKICAgIGRvY3VtZW50KGZsb2F0IHJhbmspOgogICAgICAgIHJhbmsocmFuaykKICAgIHsgfQp9OwoKdXNpbmcgZG9jX3B0ciA9IHNoYXJlZF9wdHI8ZG9jdW1lbnQ+OwoKYm9vbCBvcGVyYXRvciA8IChjb25zdCBkb2NfcHRyJiB4LCBjb25zdCBkb2NfcHRyJiB5KQp7CiAgICByZXR1cm4geC0+cmFuayA8IHktPnJhbms7Cn0KCmludCBtYWluKCkKewogICAgaW50IG4gPSAxMDsKICAgIGF1dG8gY21wX2J5X3JhbmsgPSBbXShjb25zdCBkb2NfcHRyJiB4LCBjb25zdCBkb2NfcHRyJiB5KSB7IHJldHVybiB4LT5yYW5rIDwgeS0+cmFuazsgfTsKICAgIGF1dG8gY21wX2J5X3B0ciA9IFtdKGNvbnN0IGRvY19wdHImIHgsIGNvbnN0IGRvY19wdHImIHkpIHsgcmV0dXJuIHguZ2V0KCkgPCB5LmdldCgpOyB9OwoKICAgIHZlY3Rvcjxkb2NfcHRyPiB2OwoKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBmbG9hdCByID0gc3RhdGljX2Nhc3QgPGZsb2F0PiAocmFuZCgpKSAvIHN0YXRpY19jYXN0IDxmbG9hdD4gKFJBTkRfTUFYKTsKICAgICAgICB2LmVtcGxhY2VfYmFjayhtYWtlX3NoYXJlZDxkb2N1bWVudD4ocikpOwogICAgfQoKICAgIHNvcnQodi5iZWdpbigpLCB2LmVuZCgpKTsKCiAgICBmb3IoY29uc3QgYXV0byYgZG9jOiB2KQogICAgICAgIGNvdXQgPDwgZG9jLT5yYW5rIDw8ICIgIiA8PCB1aW50NjRfdChkb2MuZ2V0KCkpIDw8IGVuZGw7CgogICAgY291dCA8PCAidiBpcyBzb3J0ZWQgPSAiIDw8IHN0ZDo6aXNfc29ydGVkKHYuYmVnaW4oKSwgdi5lbmQoKSkgPDwgZW5kbDsKICAgIGNvdXQgPDwgInYgaXMgc29ydGVkIChieSByYW5rKTogIiA8PCBpc19zb3J0ZWQodi5iZWdpbigpLCB2LmVuZCgpLCBjbXBfYnlfcmFuaykgPDwgZW5kbDsKICAgIGNvdXQgPDwgInYgaXMgc29ydGVkIChieSBwdHIpOiAiIDw8IGlzX3NvcnRlZCh2LmJlZ2luKCksIHYuZW5kKCksIGNtcF9ieV9wdHIpIDw8IGVuZGw7CiAgICBjb3V0IDw8ICItLS0tIiA8PCBlbmRsOwoKICAgIHByaW9yaXR5X3F1ZXVlPGRvY19wdHI+IHBxOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGZsb2F0IHIgPSBzdGF0aWNfY2FzdCA8ZmxvYXQ+IChyYW5kKCkpIC8gc3RhdGljX2Nhc3QgPGZsb2F0PiAoUkFORF9NQVgpOwogICAgICAgIHBxLnB1c2gobWFrZV9zaGFyZWQ8ZG9jdW1lbnQ+KHIpKTsKICAgIH0KCiAgICB2ZWN0b3I8ZG9jX3B0cj4gcHFfdjsKCiAgICB3aGlsZSghcHEuZW1wdHkoKSkgewogICAgICAgIGNvdXQgPDwgcHEudG9wKCktPnJhbmsgPDwgIiAiIDw8IHVpbnQ2NF90KHBxLnRvcCgpLmdldCgpKSA8PCBlbmRsOwogICAgICAgIHBxX3YucHVzaF9iYWNrKHBxLnRvcCgpKTsKICAgICAgICBwcS5wb3AoKTsKICAgIH0KCiAgICBjb3V0IDw8ICJwcV92IGlzIHNvcnRlZDogIiA8PCBpc19zb3J0ZWQocHFfdi5yYmVnaW4oKSwgcHFfdi5yZW5kKCkpIDw8IGVuZGw7CiAgICBjb3V0IDw8ICJwcV92IGlzIHNvcnRlZCAoYnkgcmFuayk6ICIgPDwgaXNfc29ydGVkKHBxX3YucmJlZ2luKCksIHBxX3YucmVuZCgpLCBjbXBfYnlfcmFuaykgPDwgZW5kbDsKICAgIGNvdXQgPDwgInBxX3YgaXMgc29ydGVkIChieSBwdHIpOiAiIDw8IGlzX3NvcnRlZChwcV92LnJiZWdpbigpLCBwcV92LnJlbmQoKSwgY21wX2J5X3B0cikgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQo=