Pagini recente » Cod sursa (job #988704) | Cod sursa (job #1228015) | Cod sursa (job #1787234) | Cod sursa (job #799094) | Cod sursa (job #1166593)
#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 Random(const int &st, const int &dr)
{
return st+(rand()%(dr-st+1));
}
inline int part(int st, int dr)
{
int i = st - 1, j = dr + 1, val = V[Random(st,dr)];
while (1)
{
do
{
++i;
} while (V[i] < val);
do
{
--j;
} while (val < V[j]);
if (i < j)
{
swap(V[i], V[j]);
}
else
{
return j;
}
}
}
int sdo(int st, int dr, int k)
{
if (st == dr)
{
return V[st];
}
int p = part(st,dr);
if (k<=p-st+1)
{
return sdo(st, p, k);
}
else
{
return sdo(p + 1, dr, k - (p-st+1));
}
}
int main()
{
//srand(time(NULL));
srand(30);
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;
}