Pagini recente » Cod sursa (job #731719) | Cod sursa (job #1600449) | Cod sursa (job #1308020) | Cod sursa (job #1600448) | Cod sursa (job #1972490)
#include <ctime>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int const nmax = 3000000;
int v[1 + nmax], n, k;
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];
in.close();
out << kthelement(1, n, k);
out.close();
return 0;
}