Pagini recente » Cod sursa (job #661190) | Cod sursa (job #1402955) | Cod sursa (job #946813) | Cod sursa (job #1897806) | Cod sursa (job #2909837)
#include <fstream>
#include <vector>
std::ifstream cin("sdo.in");
std::ofstream cout("sdo.out");
int select(std::vector<int> &v, int l, int r, int stat) {
if (r - l + 1 == 1) {
return v[l];
}
int piv = v[l + rand() % (r - l + 1)];
int rg = r;
for (int i = l; i <= r;) {
if (v[i] >= piv) {
std::swap(v[i], v[rg]);
rg--;
} else {
i++;
}
if (i > rg) {
break;
}
}
if (rg - l + 1 == stat) {
return piv;
}
if (rg - l + 1 > stat) {
return select(v, l, rg, stat);
}
return select(v, rg + 1, r, stat - (rg - l + 1));
}
int main() {
int n, k;
cin >> n >> k;
std::vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << select(v, 0, n - 1, k - 1);
return 0;
}