Cod sursa(job #965657)

Utilizator Theorytheo .c Theory Data 24 iunie 2013 13:31:19
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
//Heap constructed in O(n) with N elements, BFS search

#include<fstream>
#include<queue>
#include<algorithm>

using namespace std;

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

const int Nmax = 3000009;

int N; int K; int H[Nmax];


void Read(){

    fin >> N >> K;
    for(int i = 1; i <= N; ++i)
        fin >> H[i];
}

void Percolate(int Pos){

    int NextPos = Pos;

    if( (Pos << 1) <= N && H[Pos << 1] < H[NextPos]) NextPos = (Pos << 1);

    if( (Pos << 1) + 1 <= N && H[ (Pos << 1) + 1] < H[NextPos]) NextPos = (Pos << 1) + 1;

    if(Pos != NextPos ){

        swap(H[NextPos] , H[Pos]);
        Percolate(NextPos);
    }

}

void BuildHeap(){

    for(int i = N; i >= 1; --i)  Percolate(i);

}

class cmp{

    public: bool operator()(const int &X, const int &Y){
        return H[X] > H[Y];
    }
};

void BFS(){

    priority_queue< int, vector<int> , cmp> Q; Q.push(1);

    for(int i = 1; i < K; ++i){

        int t = Q.top();
        Q.pop();

        if(Q.size() == K) continue;//the lowest k numbers, useless to reatin more

        if(t * 2 <= N) Q.push(t * 2);
        if(t * 2 + 1 <= N) Q.push(t * 2 + 1);
    }

    fout << H[Q.top()];

    //while(!Q.empty()) Q.pop();

}

int main(){

    Read ();

    BuildHeap ();

    BFS();

    return 0;
}