Cod sursa(job #374082)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 15 decembrie 2009 21:57:09
Problema Statistici de ordine Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#define infile "sdo.in"
#define outfile "sdo.out"
#define nmax (3000*1000+1)
#define smax (9*nmax)
char s[smax]; //vectorul in care parsam citirea
int v[nmax]; //vectorul cu numerele
int n; //numarul de numere
int k; //trebuie sa aflam a k-a valoare din vectorul sortat
int val; //valoarea cautata

void top(int fiu)
{ //trebuie urcat elementul pana la pozitia corecta
	int tata=fiu>>1;
	int x=v[fiu];
	while(tata&&v[tata]>x)
		v[fiu]=v[tata],fiu=tata,tata>>=1;
	v[fiu]=x;
}

void down(int tata)
{ //trebuie coborat elementul pana la pozitia corecta
	int fiu=tata<<1;
	int x=v[tata];
	while(fiu<=n)
	{
		if(fiu<n && v[fiu+1]<v[fiu]) fiu++;
		if(x>v[fiu]) v[tata]=v[fiu],tata=fiu,fiu<<=1;
		else break;
	}
	v[tata]=x;
}

void extrag()
{
	v[1]=v[n--];
	down(1);
}

void read()
{
	int i,j;
	scanf("%d %d\n",&n,&k);
	fgets(s,smax,stdin);
	for(i=0,j=1;s[i];i++,j++)
	{
		while(s[i]<'0' || s[i]>'9') i++; //sarim peste caracterele
		while(s[i]>='0' && s[i]<='9') v[j]=v[j]*10+s[i++]-'0'; //construim numarul
	}
}

void init()
{
	int i;
	
	//transformam vectorul intr-un heap
	for(i=n/2;i>0;i--)
		down(i);
}

void solve()
{
	int i;
	
	//extragem primele k-1 valori
	for(i=1;i<k;i++) extrag();
	
	//salvam valoarea
	val=v[1];
}

void write()
{
	printf("%d\n",val);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}