Cod sursa(job #393976)

Utilizator alexandru92alexandru alexandru92 Data 10 februarie 2010 12:09:38
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
/* 
 * 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;
}