Pagini recente » Cod sursa (job #3284121) | Cod sursa (job #537193) | Cod sursa (job #3185531) | Cod sursa (job #1715962) | Cod sursa (job #645767)
Cod sursa(job #645767)
//SC
//10-12-11
#include <fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int n, k, a[3000000];
int partition(int a[], int l, int r){
int x = a[l];// + rand()%(r - l + 1)];
int aux;
aux = x; x = a[r]; a[r] = x;
int k, p = l - 1;
for(k = l; k <= r; k++){
if(a[k] < x){
p++;
aux = a[k]; a[k] = a[p]; a[p] = aux;
}
}
a[r] = a[++p];
a[p] = x;
return p;
}
int sdo(int a[], int l, int r, int k){
if(l == r)
return a[l];
int q = partition(a, l, r);
int len = q - l + 1;
if(len == k)
return a[q];
if(k < len)
return sdo(a, l, q-1, k);
return sdo(a, q+1, r, k-len);
}
int main()
{
int i;
srand(time(NULL));
ifstream f("sdo.in");
ofstream g("sdo.out");
f >> n >> k;
for(i = 0; i < n; i++)
f >> a[i];
g << sdo(a, 0, n-1, k) << "\n";
return 0;
}