Pagini recente » Cod sursa (job #2716260) | Cod sursa (job #3232780) | Cod sursa (job #323408) | Cod sursa (job #2966987) | Cod sursa (job #645763)
Cod sursa(job #645763)
//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 = a[x]; a[x] = a[l]; a[l] = aux;
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[++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;
}