#include <algorithm>
#include <iostream>
#include <vector>
struct MyOwnClass { int score; } ;
std:: size_t get_index_of_nth_greatest( const std:: vector < MyOwnClass> & v, std:: size_t k)
{
std:: vector < std:: size_t > indexes( v.size ( ) ) ;
std:: iota ( indexes.begin ( ) , indexes.end ( ) , 0 ) ;
std:: nth_element ( indexes.begin ( ) , indexes.begin ( ) + k, indexes.end ( ) ,
[ & ] ( int lhs, int rhs)
{
return v[ lhs] .score > v[ rhs] .score ;
}
) ;
return indexes[ k] ;
}
int main( )
{
std:: vector < MyOwnClass> scores = { { 2 } , { 42 } , { 5 } , { 21 } , { 1 } , { 3 } } ;
for ( std:: size_t i = 0 ; i ! = scores.size ( ) ; ++ i) {
const auto index = get_index_of_nth_greatest( scores, i) ;
std:: cout << i << "th greater is at index " << index
<< " with value " << scores[ index] .score << std:: endl ;
}
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKc3RydWN0IE15T3duQ2xhc3MgeyBpbnQgc2NvcmU7IH07CgpzdGQ6OnNpemVfdCBnZXRfaW5kZXhfb2ZfbnRoX2dyZWF0ZXN0KGNvbnN0IHN0ZDo6dmVjdG9yPE15T3duQ2xhc3M+JiB2LCBzdGQ6OnNpemVfdCBrKQp7CiAgICBzdGQ6OnZlY3RvcjxzdGQ6OnNpemVfdD4gaW5kZXhlcyh2LnNpemUoKSk7CiAgICBzdGQ6OmlvdGEoaW5kZXhlcy5iZWdpbigpLCBpbmRleGVzLmVuZCgpLCAwKTsKCiAgICBzdGQ6Om50aF9lbGVtZW50KGluZGV4ZXMuYmVnaW4oKSwgaW5kZXhlcy5iZWdpbigpICsgaywgaW5kZXhlcy5lbmQoKSwKICAgICAgICBbJl0oaW50IGxocywgaW50IHJocykKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB2W2xoc10uc2NvcmUgPiB2W3Joc10uc2NvcmU7CiAgICAgICAgfQogICAgKTsKICAgIHJldHVybiBpbmRleGVzW2tdOwp9CgoKaW50IG1haW4oKQp7CiAgICBzdGQ6OnZlY3RvcjxNeU93bkNsYXNzPiBzY29yZXMgPSB7ezJ9LCB7NDJ9LCB7NX0sIHsyMX0sIHsxfSwgezN9fTsKCiAgICBmb3IgKHN0ZDo6c2l6ZV90IGkgPSAwOyBpICE9IHNjb3Jlcy5zaXplKCk7ICsraSkgewogICAgICAgIGNvbnN0IGF1dG8gaW5kZXggPSBnZXRfaW5kZXhfb2ZfbnRoX2dyZWF0ZXN0KHNjb3JlcywgaSk7CiAgICAgICAgc3RkOjpjb3V0IDw8IGkgPDwgInRoIGdyZWF0ZXIgaXMgYXQgaW5kZXggIiA8PCBpbmRleAogICAgICAgICAgICA8PCAiIHdpdGggdmFsdWUgIiA8PCBzY29yZXNbaW5kZXhdLnNjb3JlIDw8IHN0ZDo6ZW5kbDsKICAgIH0KfQo=