Cod sursa(job #659163)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 10 ianuarie 2012 12:02:25
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <algorithm>

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;
}

inline int fiu_stang(int nod){
  return nod<<1;
}

inline int fiu_drept(int nod){
  return (nod<<1)+1;
}



void cerne(int n, int k){
  int fiu;
  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){
      swap(h[k], h[fiu]);
      k=fiu;
    }
  } while (fiu);
}
      
/*void urca(int n, int k){
  int key = h[k];
  while ((k>1)&&(key<h[tata(k)])){
    h[k]=h[tata(k)];
    k=tata(k);
  }
  h[k]=key;
}
*/
void build(int n){
  for (int i=n/2; i>0; i--){
    cerne(n,i);
  }
}
/*
void sterge(int &n, int k){
  h[k]=h[n];
  n--;
  if ((k>1)&&(h[k]<h[tata(k)])){
    urca(n,k);
  } else {
    cerne (n,k);
  }
}
  
void heapsort(int n){
  for (int i=n;i>=2;i--){
    swap(h[1],h[i]);
    cerne(i-1,1);
  }
}*/


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

int main()
{

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