Pagini recente » Cod sursa (job #3311513) | Cod sursa (job #2886285) | Monitorul de evaluare | Cod sursa (job #1649484) | Cod sursa (job #374084)
Cod sursa(job #374084)
#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;
}