Cod sursa(job #837879)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 18 decembrie 2012 19:42:02
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int X[3000001],n,i,k;

void sch(int &a, int &b)
{
	int aux;
	aux=a;
	a=b;
	b=aux;
}

int sdo(int st, int dr, int k)
// returneaza elementul care este al k-lea intre elementele din [st..dr]
// k este o pozitie valida, de la 1 la dr-st+1
{
	int i,j,dir,nro;
	if (st==dr)
		return X[st];
	i=st;
	j=dr;
	dir=1;
	while (i!=j)
		if (dir==1)
			if (X[i]<=X[j])
				i++;
			else
			{
				sch(X[i],X[j]);
				dir=-1;
				j--;
			}
		else
			if (X[i]<=X[j])
				j--;
			else
			{
				sch(X[i],X[j]);
				dir=1;
				i++;
			}
	nro=i-st+1;
	if (k==nro)
		return X[i];
	if (k<nro)
		return sdo(st,i-1,k);
	return sdo(i+1,dr,k-i);
}
int main()
{
	f>>n>>k;
	for(i=1;i<=n;i++)
		f>>X[i];
	g<<sdo(1,n,k)<<endl;
	f.close();
	g.close();
	return 0;
}