Pagini recente » Cod sursa (job #2878517) | Cod sursa (job #2536047) | Cod sursa (job #2791192) | Cod sursa (job #1592895) | Cod sursa (job #1310898)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 3000000;
int v[NMAX];
int nth(int *v, int st, int dr, int k) {
if (st == dr) return v[st];
int poz = st + rand() % (dr - st + 1);
int piv = v[poz],
i = st, j = dr;
while (i <= j) {
while (v[i] < piv) i++;
while (v[j] > piv) j--;
if (i <= j) {
swap(v[i], v[j]);
i++; j--;
}
}
int t = j - st + 1;
if (t >= k)
return nth(v, st, j, k);
else
return nth(v, j + 1, dr, k - t);
}
int main() {
freopen("sdo.in", "r", stdin);
freopen("sdo.out", "w", stdout);
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}
printf("%d\n", nth(v, 0, n - 1, k));
return 0;
}