Cod sursa(job #645763)

Utilizator c_sebiSebastian Crisan c_sebi Data 10 decembrie 2011 14:48:20
Problema Statistici de ordine Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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 x = a[l];// + rand()%(r - l + 1)];
    int aux;
    //aux = a[x]; a[x] = a[l]; a[l] = aux;
    int k, p = l - 1;
    for(k = l; k <= r; k++){
        if(a[k] < x){
            p++;
            aux = a[k]; a[k] = a[p]; a[p] = aux;
        }
    }
    a[++p] = x;
    return p;
}

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;
}