Cod sursa(job #373248)
Utilizator | Data | 13 decembrie 2009 03:14:52 | |
---|---|---|---|
Problema | Statistici de ordine | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <fstream>
using namespace std;
const int NMAX=3000003;
int N,K,x[NMAX];
int kth(int l,int r,int k)
{
if (l==r) return x[l];
int i=l,j=r,piv=x[l+rand()%(r-l+1)];
do
{
while (x[i]<piv) ++i;
while (x[j]>piv) --j;
if (i<=j)
{
int t=x[i];x[i]=x[j];x[j]=t;
++i;--j;
}
}while (i<=j);
if (j-l+1>=k) return kth(l,j,k);
return kth(j+1,r,k-j+l-1);
}
int main()
{
int i;
ifstream f("sdo.in");
ofstream g("sdo.out");
f>>N>>K;
for (i=1;i<=N;++i) f>>x[i];
g<<kth(1,N,K);
return 0;
}