#include <algorithm>
#include <vector>
#include <iostream>
template<typename Vector>
std::vector<double> rank(const Vector& v)
{
std::vector<std::size_t> w(v.size());
std::iota(begin(w), end(w), 0);
std::sort(begin(w), end(w),
[&v](std::size_t i, std::size_t j) { return v[i] < v[j]; });
std::vector<double> r(w.size());
for (std::size_t n, i = 0; i < w.size(); i += n)
{
n = 1;
while (i + n < w.size() && v[w[i]] == v[w[i+n]]) ++n;
for (std::size_t k = 0; k < n; ++k)
{
r[w[i+k]] = i + (n + 1) / 2.0; // average rank of n tied values
// r[w[i+k]] = i + 1; // min
// r[w[i+k]] = i + n; // max
// r[w[i+k]] = i + k + 1; // random order
}
}
return r;
}
int main()
{
std::vector<int> v = { 7, 3, 1, 3, 5 };
std::vector<double> ranks = rank(v);
for (std::size_t i = 0; i < v.size(); ++i)
std::cout << v[i] << " : " << ranks[i] << '\n';
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdGVtcGxhdGU8dHlwZW5hbWUgVmVjdG9yPgpzdGQ6OnZlY3Rvcjxkb3VibGU+IHJhbmsoY29uc3QgVmVjdG9yJiB2KQp7CglzdGQ6OnZlY3RvcjxzdGQ6OnNpemVfdD4gdyh2LnNpemUoKSk7CglzdGQ6OmlvdGEoYmVnaW4odyksIGVuZCh3KSwgMCk7CglzdGQ6OnNvcnQoYmVnaW4odyksIGVuZCh3KSwgCgkJWyZ2XShzdGQ6OnNpemVfdCBpLCBzdGQ6OnNpemVfdCBqKSB7IHJldHVybiB2W2ldIDwgdltqXTsgfSk7CgoJc3RkOjp2ZWN0b3I8ZG91YmxlPiByKHcuc2l6ZSgpKTsKCWZvciAoc3RkOjpzaXplX3QgbiwgaSA9IDA7IGkgPCB3LnNpemUoKTsgaSArPSBuKQoJewoJCW4gPSAxOwoJCXdoaWxlIChpICsgbiA8IHcuc2l6ZSgpICYmIHZbd1tpXV0gPT0gdlt3W2krbl1dKSArK247CgkJZm9yIChzdGQ6OnNpemVfdCBrID0gMDsgayA8IG47ICsraykKCQl7CgkJCXJbd1tpK2tdXSA9IGkgKyAobiArIDEpIC8gMi4wOyAvLyBhdmVyYWdlIHJhbmsgb2YgbiB0aWVkIHZhbHVlcwoJCQkvLyByW3dbaStrXV0gPSBpICsgMTsgICAgIC8vIG1pbiAKCQkJLy8gclt3W2kra11dID0gaSArIG47ICAgICAvLyBtYXgKCQkJLy8gclt3W2kra11dID0gaSArIGsgKyAxOyAvLyByYW5kb20gb3JkZXIKCQl9Cgl9CglyZXR1cm4gcjsKfQoKaW50IG1haW4oKQp7CglzdGQ6OnZlY3RvcjxpbnQ+IHYgPSB7IDcsIDMsIDEsIDMsIDUgfTsgCglzdGQ6OnZlY3Rvcjxkb3VibGU+IHJhbmtzID0gcmFuayh2KTsKCQoJZm9yIChzdGQ6OnNpemVfdCBpID0gMDsgaSA8IHYuc2l6ZSgpOyArK2kpCgkJc3RkOjpjb3V0IDw8IHZbaV0gPDwgIiA6ICIgPDwgcmFua3NbaV0gPDwgJ1xuJzsgCgoJcmV0dXJuIDA7Cn0=