Pagini recente » Cod sursa (job #667140) | Cod sursa (job #1522071) | Cod sursa (job #1782631) | Cod sursa (job #1563032) | Cod sursa (job #2374707)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int const NMAX = 3 * 1e6;
int n, k;
int v[1 + NMAX];
int kthelement(int a, int b, int k) {
if(a < b) {
int ipivot = a + rand() % (b - a + 1);
int pivot = v[ipivot];
int i = a - 1;
int j = a;
while(j <= b){
if(v[j] <= pivot) {
i++;
swap(v[i], v[j]);
}
j++;
}
if(k <= i - a + 1)
return kthelement(a, i, k);
else
return kthelement(i + 1, b, k - (i - a + 1));
} else {
return v[a];
}
}
int main() {
srand(time(NULL));
in >> n >> k;
for(int i = 1; i <= n; i++)
in >> v[i];
out << kthelement(1, n, k);
in.close();
out.close();
return 0;
}