Pagini recente » Cod sursa (job #395624) | Cod sursa (job #793966) | Cod sursa (job #2882787) | Cod sursa (job #1602668) | Cod sursa (job #2621800)
#include <iostream>
#include <fstream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int l,n,i,v[3000001];
int separare(int st,int dr,int v[]){
int pivot=dr,i=st,j;
for(j=st;j<dr;j++) //cautam pozitia pivotului
if(v[j]<v[pivot]){
swap(v[i],v[j]);
i++;
}
swap(v[pivot],v[i]);
return i;
}
int def_pivot(int st,int dr,int v[]){
int pivot,r;
r=rand();
pivot=st+r%(dr-st+1); //alegem pivotul random
swap(v[dr],v[pivot]);
return separare(st,dr,v);
}
int quick(int st,int dr,int v[],int val){//alg asemanator cu quick sort dar se ocupa de anumite portiuni ce ajuta la determinarea solutiei
int i,poz;
if(st==dr)
return v[st];
i=def_pivot(st,dr,v); //definim pivotul random
poz=i-st+1;
if(val<=poz) //ne orientam doar pe portiunea ce contine valoarea
quick(st,i,v,val);
else
quick(i+1,dr,v,val-poz);
}
int main() {
in>>n>>l;
for( i=1;i<=n;i++)
in>>v[i];
out<<quick(1,n,v,l);
return 0;
}