Cod sursa(job #371237)

Utilizator Mishu91Andrei Misarca Mishu91 Data 4 decembrie 2009 15:36:46
Problema Statistici de ordine Scor Ascuns
Compilator cpp Status done
Runda Marime 0.66 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX_N 3000005

int N, K, A[MAX_N];

ifstream fin ("sdo.in");
ofstream fout ("sdo.out");

void citire()
{
	fin >> N >> K;

	for(int i = 1; i <= N; ++i)
		fin >> A[i];

	make_heap(A+1, A+N+1, greater <int> ());
}

struct cmp
{
	bool operator() (const int &a, const int &b)
	{
		return A[a] > A[b];
	}
};

void solve()
{
	priority_queue <int, vector <int>, cmp > Q;

	Q.push(1);
	for(int i = 1; i < K; ++i)
	{
		int k = Q.top();
		Q.pop();
		if(Q.size() == K) continue;
		if(2*k <= N)Q.push(2*k);
		if(2*k < N) Q.push(2*k+1);
	}

	fout << A[Q.top()];
}

int main()
{
	citire();
	solve();
}