Pagini recente » Robert Hangu | C.C. | Monitorul de evaluare | Profil Robert Hangu | Cod sursa (job #1736738)
#include <fstream>
using namespace std;
#define MAX 3000000
ifstream in("sdo.in");
ofstream out("sdo.out");
int n,k;
int v[MAX];
int partition(int v[MAX],int p,int r) {
int temp,i=p-1,x=v[r];
for (int j=p;j<r;j++) {
if (v[j]<=x) {
i++;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
}
temp=v[i+1];
v[i+1]=v[r];
v[r]=temp;
return i+1;
}
int kThMin(int v[MAX],int low,int high,int k) {
int pos;
pos=partition(v,low,high);
if (pos-low+1==k)
return v[pos];
else if (pos-low+1>k)
return kThMin(v,low,pos-1,k);
else
return kThMin(v,pos+1,high,k-pos+low-1);
}
int main() {
in>>n>>k;
for (int i=0;i<n;i++)
in>>v[i];
out<<kThMin(v,0,n-1,k);
return 0;
}