Cod sursa(job #2127540)

Utilizator horiainfoTurcuman Horia horiainfo Data 10 februarie 2018 18:58:16
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
/*
    ID : thoria1991
    TASK : barn1
    LANG : C++11
*/
 
#include <bits/stdc++.h>

using namespace std;

int n, a[3000002], k;

int part(int st, int end, int k){

    int e = a[st + rand() % (end - st + 1)];

    while(true){

        while(a[st] < e) st ++;
        while(a[end] > e) end --;

        if(st < end)    swap(a[st], a[end]);
        else            return end;
    }
}

void select(int st, int end, int k){

    if(st == end) return;

    int p = part(st, end, k);
    int nr = p - st + 1;
    
    if(nr >= k) select(st, p, k);
    else        select(p + 1, end, k - nr); 
}

int main(){

    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    select(1, n, k);
    cout << a[k]; cin >> n;
}