Pagini recente » Cod sursa (job #2592121) | Cod sursa (job #2673324) | Cod sursa (job #767866) | Cod sursa (job #2875287) | Cod sursa (job #542300)
Cod sursa(job #542300)
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
const char InFile[]="sdo.in";
const char OutFile[]="sdo.out";
const int MaxN=3000111;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,K,V[MaxN];
inline int randomInt(int minv, int maxv)
{
return minv+(rand()%(maxv-minv+1));
}
inline int partition(int st, int dr)
{
int pivot=V[randomInt(st,dr)];
--st;
++dr;
while(true)
{
do
{
++st;
}while(V[st]<pivot);
do
{
--dr;
}while(pivot<V[dr]);
if(st<dr)
{
swap(V[st],V[dr]);
}
else
{
return dr;
}
}
return 0;
}
int sdo(int st, int dr, int pos)
{
if(st==dr)
{
return V[st];
}
int m=partition(st,dr);
int left=m-st+1;
if(pos<=left)
{
return sdo(st,m,pos);
}
return sdo(m+1,dr,pos-left);
}
int main()
{
srand((unsigned int)(time(NULL)));
fin>>N>>K;
for(register int i=1;i<=N;++i)
{
fin>>V[i];
}
fin.close();
fout<<sdo(1,N,K);
fout.close();
return 0;
}