Pagini recente » Cod sursa (job #1907006) | Cod sursa (job #2971540) | Cod sursa (job #122929) | Cod sursa (job #3040171) | Cod sursa (job #2555868)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define MAXN 3000001
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int N, K, v[MAXN];
struct number_in_heap {
int position, value;
number_in_heap(int pos, int val) {
position = pos;
value = val;
}
inline bool operator < (const number_in_heap &x) const {
return value > x.value;
}
};
bool cmp(int a, int b) {
return a > b;
}
void read() {
f >> N >> K;
for (int i = 1; i <= N; ++i) {
f >> v[i];
}
make_heap(v + 1, v + N + 1, cmp);
}
// O(n + klogk) - solution
int solve_heap_bfs() {
priority_queue <number_in_heap> Q;
Q.push(number_in_heap(1, v[1]));
for (int i = 1; i < K; ++i) {
number_in_heap aux = Q.top();
Q.pop();
if (2 * aux.position <= N) {
number_in_heap tmp = number_in_heap(2 * aux.position, v[2 * aux.position]);
Q.push(tmp);
}
if (2 * aux.position + 1 <= N) {
number_in_heap tmp = number_in_heap(2 * aux.position + 1, v[2 * aux.position + 1]);
Q.push(tmp);
}
}
return Q.top().value;
}
int main() {
read();
g << solve_heap_bfs();
return 0;
}