KStatistics

#include <iostream>
#include <vector>
#include <assert.h>
using std::cin;
using std::cout;
using std::vector;

// Разделение на две части по опорному. Возвращает позицию опорного элемента.
int Partition( vector<int>& arr, int begin, int end )
{
    // Опорным считаем последний элемент массива.
    int pivot = arr[end - 1];
    int i = begin;
    int j = end - 2;
    while( i <= j ) {
        for( ; arr[i] < pivot; ++i ) {} // Двигаем i вправо, за границу не выйдем, т.к. arr[end - 1] == pivot.
        for( ; j >= begin && arr[j] >= pivot; --j ) {} // Двигаем j влево.
        if( i < j ) {
            std::swap( arr[i], arr[j] );
        }
    }
    // Ставим опорный элемент на свое место.
    std::swap( arr[i], arr[end - 1] );
    return i;
}

int KStatistics( vector<int>& arr, int k )
{
    assert( !arr.empty() );
    int begin = 0;
    int end = arr.size();
    while( true ) {
        int pivotPos = Partition( arr, begin, end );
        if( pivotPos == k ) {
            return arr[k];
        }
        if( pivotPos > k ) { // Нужная статистика в левой части.
            end = pivotPos;
        } else {
            begin = pivotPos + 1;
        }
    }
}

int main()
{
    int n = 0;
    cin >> n;
    int k = 0;
    cin >> k;

    vector<int> arr( n, 0 );
    for( int i = 0; i < n; ++i ) {
        cin >> arr[i];
    }

    cout << KStatistics( arr, k );
    return 0;
}