Pagini recente » Cod sursa (job #1892776) | Cod sursa (job #1892264) | Cod sursa (job #1611614) | Cod sursa (job #1773412) | Cod sursa (job #393976)
Cod sursa(job #393976)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on February 9, 2010, 7:25 PM
*/
#include <fstream>
#include <iterator>
#define Nmax 3000001
/*
*
*/
using namespace std;
int N, N2=1;
int Heap[Nmax], Heap2[Nmax];
inline void swap( int& x, int& y )
{
x+=y;
y=x-y;
x-=y;
}
void DownHeap( int k )
{
int son;
while( true )
{
son=2*k;
if( son > N )
return;
if( son < N && Heap[son] > Heap[son+1] )
++son;
if( Heap[son] >= Heap[k] )
return;
swap( Heap[son], Heap[k] );
k=son;
}
}
void DownHeap2( int k )
{
int son;
while( true )
{
son=2*k;
if( son > N2 )
return;
if( son < N2 && Heap[Heap2[son]] > Heap[Heap2[son+1]] )
++son;
if( Heap[Heap2[son]] >= Heap[Heap2[k]] )
return;
swap( Heap2[son], Heap2[k] );
k=son;
}
}
void UpHeap2( int k )
{
int key=Heap[Heap2[k]], f=k/2;
while( k > 1 && key < Heap[Heap2[f]] )
{
swap( Heap2[k], Heap2[f] );
k=f;
f/=2;
}
}
int main( void )
{
int k, i, j;
ifstream in( "sdo.in" );
in>>N>>k;
copy( istream_iterator<int>(in), istream_iterator<int>(), Heap+1 );
for( i=N/2; i > 0; --i )
DownHeap( i );
Heap2[1]=1;
for( i=1; i < k; ++i )
{
j=Heap2[1];
Heap2[1]=Heap2[N2];
--N2;
DownHeap2(1);
if( N2 == k )
continue;
if( 2*j <= N )
{
Heap2[++N2]=2*j;
UpHeap2(N2);
}
if( 2*j < N )
{
Heap2[++N2]=2*j+1;
UpHeap2(N2);
}
}
ofstream out("sdo.out");
out<<Heap[Heap2[1]];
return 0;
}