Cod sursa(job #2129742)

Utilizator omegasFilip Ion omegas Data 13 februarie 2018 03:21:42
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

ifstream fin("sdo.in");
ofstream fout("sdo.out");
int v[1000001];

int partitie(int p,int r){
    int pivot;
    pivot = (rand()%(r - p + 1) + p);
    swap(v[pivot],v[r]);

    int q = r;
    for(int i=p;i<q;++i){
        if(v[i] > v[q]){
            swap(v[i],v[q-1]);
            swap(v[q],v[q-1]);
            -- q;
        }
    }
    return q;
}

int orderSelect(int p,int r,int k)
{
    int q;
    int aux;
    q = partitie(p,r);
    aux = q - p + 1;
    if(aux == k)
        return v[q];
    else if(aux > k)
        return orderSelect(p,q - 1,k);
    else
        return orderSelect(q + 1,r,k - aux);

}

int main()
{
    int n,k,x,i;
    fin >> n >> k;


    for(i=1;i<=n;++i){
        fin >> v[i];
    }
    fout << orderSelect(1,n,k);

    return 0;
}