Cod sursa(job #1257266)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 7 noiembrie 2014 15:35:58
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <ctime>
#include <algorithm>
using namespace std;
int n, v[3000100], sol;

inline int NthElement(int st, int dr, int K)
{
    if(st == dr)
        return v[st];
    int poz = st + rand() % (dr - st + 1);
    int pivot = v[poz], i = st, j = dr;
    while(i <= j)
    {
        while(v[i] < pivot)
            i++;
        while(v[j] > pivot)
            j--;
        if(i <= j)
        {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }
    if(K <= j - st + 1)
        return NthElement(st, j, K);
    return NthElement(j + 1, dr, K - (j - st + 1));
}

int main()
{
    int i, K;
    ifstream fin("sdo.in");
    fin >> n >> K;
    for(i = 1; i <= n; ++i)
        fin >> v[i];
    fin.close();

    srand(time(NULL));
    sol = NthElement(1, n, K);

    ofstream fout("sdo.out");
    fout << sol << "\n";
    fout.close();
    return 0;
}