Pagini recente » Cod sursa (job #1793736) | Cod sursa (job #1614791) | Cod sursa (job #2591112) | Cod sursa (job #1295915) | Cod sursa (job #373335)
Cod sursa(job #373335)
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fi("sdo.in");
ofstream fo("sdo.out");
int N,A[3000010],K;
int poz(int* A,int p,int u){
int pivot=A[p+(rand()%(u-p+1))];
int start=p,end=u;
for (;1;){
while (A[start]<pivot) ++start;
while (A[end]>pivot) --end;
if (start<end){ int aux=A[start];A[start]=A[end];A[end]=aux; }
else return start;
}
}
int kth_elem(int *A,int p,int u,int k){
int m=poz(A,p,u);
int x=m-p+1;
if (x>k) return kth_elem(A,p,m-1,k); else
if (x<k)
return kth_elem(A,m+1,u,k-x); else return A[m];
}
int main(){
srand(time(NULL));
fi>>N>>K;
for (int i=1;i<=N;++i) fi>>A[i];
fo<<kth_elem(A,1,N,K);
fi.close();fo.close();
return 0;
}