Cod sursa(job #2484389)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 31 octombrie 2019 01:45:49
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define nmax 3000005
using namespace std;
int n, k, a[nmax];
int partitionn(int st, int dr){
    int len = (dr - st + 1);
    int wh = rand() % len;
    swap(a[st],a[st+wh]);
    int piv = a[st];
    while (st < dr){
        while (st < dr && a[dr] >= piv) --dr;
        a[st] = a[dr];
        while (st < dr && a[st] <= piv) ++st;
        a[dr] = a[st];
    }
    a[st] = piv;
    return st;
}
int di(int st, int dr){
    if (st == dr){
        if (st == k){
            return a[k];
        } else {
            return -1;
        }
    }
    int pos = partitionn(st, dr);
    if (pos == k){
        return a[k];
    }
    else if (pos > k){
        return di(st,pos-1);
    } else {
        return di(pos+1,dr);
    }
}
int main()
{
    freopen("sdo.in","r",stdin);
    freopen("sdo.out","w",stdout);
    scanf("%d %d",&n,&k);
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    printf("%d\n", di(1,n));
    return 0;
}