Pagini recente » Cod sursa (job #1788925) | Cod sursa (job #1203353) | Cod sursa (job #1525445) | Cod sursa (job #860464) | Cod sursa (job #837879)
Cod sursa(job #837879)
#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;
}