Pagini recente » Cod sursa (job #467825) | Cod sursa (job #3214371) | Cod sursa (job #3195335) | Cod sursa (job #2604211) | Cod sursa (job #1007818)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
const int N = 3000000;
int v[N];
/* Find buckets_no in logarithmic time */
int buckets_no(int x) {
int step = 15, i;
for (i = 0; step; step >>= 1) {
if ((i + step) *(i + step) <= x)
i += step;
}
return i;
}
int solve(int *v, int k, int n) {
int sq = buckets_no(n) , min = 0, max = INT_MAX, index = k;
int *frecv = new int[sq+1];
while (index) {
if (min == max) {
return v[0];
}
memset(frecv, 0, (sq+1) * sizeof(int));
int bucket_range = (max - min) / sq;
for (int i = 0; i < n; ++ i) {
frecv[ (v[i] - min) / bucket_range ]++;
}
for (int i = 0; i <= sq; ++i) {
if (index - frecv[i] > 0) {
index -= frecv[i];
} else {
min = min + i * bucket_range;
max = min + bucket_range -1;
for ( int j = 0, aux = 0; j < n ; ++j) {
if (v[j] >= min && v[j] <= max ){
v[aux++] = v[j];
}
}
n = frecv[i];
break;
}
}
sq = buckets_no(n);
}
return -1;
}
int main() {
int n, k;
in>>n>>k;
for (int i = 0; i < n; ++i) {
in>>v[i];
}
out<<solve(v, k, n)<< "\n";
return 0;
}