Pagini recente » Cod sursa (job #1779553) | Cod sursa (job #2509515) | Cod sursa (job #27287) | Cod sursa (job #1313998) | Cod sursa (job #645779)
Cod sursa(job #645779)
//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 aux, x = a[l + rand()%(r - l + 1)];
int i = l - 1, j = r + 1;
while(1){
do{
i++;
} while(a[i] < x);
do{
j--;
} while(x < a[j]);
if(i < j){
aux = a[i]; a[i] = a[j]; a[j] = aux;
}
else return j;
}
}
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;
}