Pagini recente » Cod sursa (job #19404) | Cod sursa (job #1987129)
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
int n, t, v[3000005];
int pivot(int l, int r)
{
int piv = rand()%(r-l) + l;
int st = l, dr = r, x = v[piv];
while(st < dr){
while(st < dr && v[dr] >= x)
--dr;
v[st] = v[dr];
while(st < dr && v[st] <= x)
++st;
v[dr] = v[st];
}
v[st] = x;
return st;
}
int quick_select(int l, int r)
{
int m = pivot(l, r);
if(m == t)
return v[m];
if(m-1 > l && m > t)
return quick_select(l, m-1);
else if(m+1 < r && m < t)
return quick_select(m+1, r);
return v[1];
}
int main()
{
srand(time(NULL));
ifstream fin ("sdo.in");
ofstream fout ("sdo.out");
fin >> n >> t;
for (int i = 1; i <= n; ++i)
fin >> v[i];
fout << quick_select(1, n);
return 0;
}