Pagini recente » Borderou de evaluare (job #258466) | Rezultatele filtrării | Cod sursa (job #204215) | Rezultatele filtrării | Cod sursa (job #469243)
Cod sursa(job #469243)
#include <cstdio>
#include <cstdlib>
#include <ctime>
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]);
V[i] = i;
}
}
void swap(int &a, int &b) {
int aux;
aux = a; a = b; b = aux;
}
void solve() {
// set left and right
int L = 1, R = N;
// randomize
srand(time(0));
// do it
while (1) {
// create random
int r = L + rand() % (R - L + 1);
int F = V[r], aux, k;
// iterate smaller than V
k = 0;
for (int i = L; i <= R; ++i) {
if (V[i] < F) {
swap(V[L + k], V[i]);
if (V[i] == F) r = i;
++k;
}
}
swap(V[L + k], V[r]);
// where is it?
if (K < k + L) {
// is it done?
if (k == 1) {
A = V[L];
break;
}
// on the left side
R = L + k - 1;
} else if (K <= k + L) {
// in the center :)
A = F;
break;
} else {
// is it done?
if (k == R - L - 1) {
A = V[R];
break;
}
// on the right
L = L + k + 1;
}
}
}
void write() {
// output file
freopen("sdo.out", "w", stdout);
// print answer
printf("%d\n", A);
}
int main() {
read();
solve();
write();
return 0;
}