Cod sursa(job #374084)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 15 decembrie 2009 22:10:59
Problema Statistici de ordine Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.51 kb
#include<stdio.h>
#define infile "sdo.in"
#define outfile "sdo.out"
#define nmax (3000*1000+1)
#define smax (1<<16)
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);
	fread(s,1,smax,stdin);
	for(i=0,j=1;j<=n;j++)
	{
		//sarim peste caracterele proaste
		while(s[i]<'0' || s[i]>'9')
			if(++i==smax)
				fread(s,1,smax,stdin),i=0;
		
		//construim numarul
		while(s[i]>='0' && s[i]<='9')
		{
			v[j]=v[j]*10+s[i]-'0';
			if(++i==smax)
				fread(s,1,smax,stdin),i=0;
		}
	}
}

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