Cod sursa(job #375213)

Utilizator MciprianMMciprianM MciprianM Data 19 decembrie 2009 20:37:35
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
using namespace std;
#define MAXN 3000009
unsigned int h[MAXN], hsize=1;
void insert_M(unsigned int x){
	int ind=hsize;
	h[hsize++]=x;
	while(h[ind/2]<x&&ind>1){
			h[ind]=h[ind/2];
			h[ind/2]=x;
			ind/=2;
	}
}
void insert_N(unsigned int x){
	unsigned int ind=1, imax;
	h[ind]=x;imax=ind;
	do{
		ind=imax;
		if(h[2*ind]>h[ind])
			imax=2*ind;
		if(h[2*ind+1]>h[imax])
			imax=2*ind+1;
		x=h[imax];
		h[imax]=h[ind];
		h[ind]=x;
	}while(imax!=ind && ind<hsize);
	
	while(h[ind/2]<x&&ind>1){
			h[ind]=h[ind/2];
			h[ind/2]=x;
			ind/=2;
	}
}
int main(){
	unsigned int n, k, i, x;
	ifstream f("sdo.in");
	f>>n>>k;
	for(i=0;i<k;i++){
		f>>x;
		insert_M(x);
	}
	while(i<n){
		f>>x;
		if(x<h[1])	insert_N(x);
		i++;
	}
	f.close();
	ofstream g("sdo.out");
	g<<h[1]<<'\n';
	g.close();
	return 0;
}