Cod sursa(job #645779)

Utilizator c_sebiSebastian Crisan c_sebi Data 10 decembrie 2011 15:08:31
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
//SC
//10-12-11
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int n, k, a[3000000];

int partition(int a[], int l, int r){
    int aux, x = a[l + rand()%(r - l + 1)];
    int i = l - 1, j = r + 1;
    while(1){
        do{
            i++;
        } while(a[i] < x);

        do{
            j--;
        } while(x < a[j]);

        if(i < j){
            aux = a[i]; a[i] = a[j]; a[j] = aux;
        }
        else return j;
    }
}

int sdo(int a[], int l, int r, int k){
    if(l == r)
        return a[l];
    int q = partition(a, l, r);
    int len = q - l + 1;
    if(len == k)
        return a[q];
    if(k < len)
        return sdo(a, l, q-1, k);
    return sdo(a, q+1, r, k-len);
}

int main()
{
    int i;
    srand(time(NULL));
    ifstream f("sdo.in");
    ofstream g("sdo.out");
    f >> n >> k;
    for(i = 0; i < n; i++)
        f >> a[i];
    g << sdo(a, 0, n-1, k) << "\n";
    return 0;
}