Pagini recente » Borderou de evaluare (job #1386058) | Cod sursa (job #469228)
Cod sursa(job #469228)
#include <cstdio>
#include <cstdlib>
int N, K, A;
int V[3000005];
void read() {
// input file
freopen("sdo.in", "r", stdin);
// scan n, k
scanf("%d%d", &N, &K);
// scan all
for (int i = 1; i <= N; ++i) {
scanf("%d", &V[i]);
}
}
void solve() {
// set left and right
int L = 1, R = N, s, l;
// do it
while (1) {
// create random
int F = V[L + rand() % (R - L + 1)], aux, k, l;
// iterate smaller than V
k = 0;
for (int i = L; i <= R; ++i) {
if (V[i] < F) {
aux = V[L + k];
V[L + k] = V[i];
V[i] = aux;
++k;
}
}
// iterate larger than V
l = 0;
for (int i = R; i >= L; --i) {
if (V[i] > F) {
aux = V[R - l];
V[R - l] = V[i];
V[i] = aux;
++l;
}
}
// where is it?
if (K <= k) {
// on the left side
R = L + k - 1;
} else if (K >= R - L - l + 2) {
// on the right
K -= R-L-l+1;
L = R - L - l + 2;
} else {
// in the center :)
A = F;
break;
}
}
}
void write() {
// output file
freopen("sdo.out", "w", stdout);
// print answer
printf("%d\n", A);
}
int main() {
read();
solve();
write();
return 0;
}