Cod sursa(job #371241)

Utilizator Mishu91Andrei Misarca Mishu91 Data 4 decembrie 2009 15:49:45
Problema Statistici de ordine Scor Ascuns
Compilator cpp Status done
Runda Marime 0.66 kb
#include <fstream>
#include <set>
#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()
{
	set <int, cmp > S;

	S.insert(1);
	for(int i = 1; i < K; ++i)
	{
		int k = *S.begin();
		S.erase(S.begin());
		if(S.size() == K) continue;
		if(2*k <= N)S.insert(2*k);
		if(2*k < N) S.insert(2*k+1);
	}

	fout << A[*S.begin()];
}

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