Cod sursa(job #659174)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 10 ianuarie 2012 12:11:46
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
//sdo cu heapuri
#include <fstream>
#define fiu_stang(n) (n<<1)
#define fiu_drept(n) ((n<<1)+1)

using namespace std;

int h[3000001]; 
  ifstream fin("sdo.in");
  ofstream fout("sdo.out");

inline int tata(int nod){
  return nod>>1;
}

void afis_heap(int n){
  fout<<"heap ";
  for (int i=1; i<=n;i++)
    fout<<h[i]<<" ";
  fout<<endl;
}

void cerne(int n, int k){
  int fiu,x;
  do {
    fiu=0;
    if (fiu_stang(k)<=n){
      fiu = fiu_stang(k);
      if (fiu_drept(k)<=n && h[fiu_drept(k)]<h[fiu_stang(k)]){
        fiu=fiu_drept(k);
      }
      if (h[fiu]>=h[k])
        fiu=0;
    }
    if (fiu){
      x=h[k];
      h[k]=h[fiu];
      h[fiu]=x;
      k=fiu;
    }
  } while (fiu);
}

void build(int n){
  for (int i=n/2; i>0; i--){
    cerne(n,i);
  }
}


int tzipa(int k,int n){
  if (k>1)  
    for (int i=n;k>1&&i>=2;i--){
      h[1]=h[i];
      cerne(i-1,1);
      k--;
    }
  return h[1];
}

int main()
{

  int n,k;
  fin>>n>>k;
  for (int i=1; i<=n;i++){
    fin>>h[i];
  }
  build(n);
  fout<<tzipa(k,n);
  
  return 0;
}