Порядковая статистика

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int partition(vector<int> &a,int l,int r){
    swap(a[l+rand()%(r-l+1)],a[r]);
    int mid = a[r];
    int i=l-1;
    for(int j=l;j<r;j++)
        if(a[j]<mid)
            swap(a[++i],a[j]);
    swap(a[i+1],a[r]);
    return i+1;
}
 
int get_st(vector<int> &a,int l,int r,int k){
    if(r==l) return a[r];
    int mid = partition(a,l,r);
    int c_el = mid -l+1;
    if(k==c_el)
        return a[mid];
    if(c_el>k)
        return get_st(a,l,mid-1,k);
    else
        return get_st(a,mid+1,r,k-c_el);
}
 
 
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    double res;
    if((n&1)==1)
        res = get_st(a,0,n-1,(n+1)/2);
    else {
        res = (get_st(a,0,n-1,n/2)+get_st(a,0,n-1,n/2+1)+0.0)/2;
    }
    cout.precision(10);
    cout << fixed;
    cout<<res;
    return 0;
}