Pagini recente » Cod sursa (job #1997488) | Cod sursa (job #2043679) | Cod sursa (job #180968) | Cod sursa (job #365563) | Cod sursa (job #1625469)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
void swap(int *a, int *b) {
if (*a == *b) {
return;
}
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
int partition(std::vector<int> &v, int lower, int upper) {
int pivotIndex = lower + (upper - lower) / 2;
int pivot = v[pivotIndex];
swap(&v[pivotIndex], &v[upper]);
int store = lower;
int 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;
}
int find_kth_min(std::vector<int> &v, int lower, int upper, int k) {
int 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");
int n, x;
f >> n >> x;
std::vector<int> v(n);
for (int i = 0; i < n; f >> v[i++]);
g << find_kth_min(v, 0, v.size() - 1, x - 1) << '\n';
g.close();
f.close();
}