Cod sursa(job #1183719)

Utilizator tudi98Cozma Tudor tudi98 Data 9 mai 2014 23:59:16
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <algorithm>
#define dim 3000005
using namespace std;

int n,k,a[dim];

int part(int l,int r){
    
    int pivot,i,j;
    i=l;
    j=r;
    pivot = a[l+rand()%(r-l+1)];
    do{
        while(a[i]<pivot) i++;
        while(a[j]>pivot) j--;
        if(i<j)
            swap(a[i],a[j]);
        else return j;
        
    }while(1);
    
}

void sdo(int l,int r,int k){
    
    int q,t;
    if(l==r) return;
    q=part(l,r);
    t=q-l+1;
    if(t<k){        //daca se afla in dreapta 
        sdo(t+1,r,k-t);
    }               //altfel daca se afla in stanga
    else sdo(l,t,k);       
}

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