Pagini recente » Cod sursa (job #611112) | Cod sursa (job #2888176) | Cod sursa (job #2799616) | Cod sursa (job #2537192) | Cod sursa (job #1625479)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
typedef unsigned int uint;
void swap(uint *a, uint *b) {
if (*a == *b) {
return;
}
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
int partition(std::vector<uint> &v, uint lower, uint upper) {
uint pivotIndex = lower + (upper - lower) / 2;
uint pivot = v[pivotIndex];
swap(&v[pivotIndex], &v[upper]);
uint store = lower;
uint i = upper - 1;
while (i > store) {
while (i > store && v[store] <= pivot)
store++;
while (i > store && v[i] > pivot)
i--;
if (i > store)
swap(&v[i], &v[store]);
}
if (v[store] > v[upper]) {
swap(&v[upper], &v[store]);
}
return store;
}
uint find_kth_min(std::vector<uint> &v, uint lower, uint upper, uint k) {
uint begin = lower, end = upper;
int p = partition(v, begin, end);
if (p != k) {
if (p < k) {
return find_kth_min(v, p + 1, upper, k);
} else {
return find_kth_min(v, lower, p - 1, k);
}
}
return v[k];
}
int main(void) {
std::ifstream f("sdo.in");
std::ofstream g("sdo.out");
uint n, x;
f >> n >> x;
std::vector<uint> v(n);
for (uint i = 0; i < n; f >> v[i++]);
g << find_kth_min(v, 0, v.size() - 1, x - 1) << '\n';
g.close();
f.close();
}