Pagini recente » Cod sursa (job #2805552) | Cod sursa (job #2679918) | Cod sursa (job #741377) | Cod sursa (job #1909250) | Cod sursa (job #1546099)
#include<iostream>
#include<fstream>
#include<cstdlib>
#define FIN "sdo.in"
#define FOUT "sdo.out"
#define MAXN 3000001
using namespace std;
ifstream f(FIN);
ofstream g(FOUT);
int n, k, v[MAXN];
int solve(int left, int right, int k)
{
if(left == right)
return v[left];
int pivot = v[(rand() % right - left + 1) + left + 1];
int i = left;
int j = right;
while(i < j)
{
while(v[i] < pivot)
{
i++;
}
while(v[j] > pivot)
{
j--;
}
if(i <= j)
{
swap(v[i], v[j]);
i++;
j--;
}
}
int pos = j - left + 1;
if(pos >= k)
{
return solve(left, j, k);
}
else
{
return solve(pos + 1, right, k - i);
}
return 0;
}
int main()
{
f >> n;
f >> k;
for(int i=1; i<=n; i++)
f >> v[i];
g << solve(1, n, k);
return 0;
}