Pagini recente » Cod sursa (job #2103025) | Cod sursa (job #1556053) | Profil M@2Te4i | Istoria paginii utilizator/ysaika2 | Cod sursa (job #2277151)
#include <iostream>
#include <fstream>
#include <random>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
const int N = 3000001;
int n, v[N], k;
int partitie (int v[], int st, int dr) {
int ra=st+rand()%(dr-st+1);
int rb=st+rand()%(dr-st+1);
int rc=st+rand()%(dr-st+1);
if(v[ra]>v[rb])
{
swap(ra,rb);
}
if(v[ra]>v[rc])
{
swap(ra,rc);
}
if(v[rb]>v[rc])
{
swap(rb,rc);
}
int poz=rb;
swap(v[dr],v[poz]);
int pivot = v[dr];
int i=st-1;
int j=dr+1;
while(1)
{
do
{
i++;
}
while(v[i]<pivot);
do
{
j--;
}
while(v[j]>pivot);
if(i>=j)
{
return j;
}
swap(v[i],v[j]);
}
}
void sdo (int v[], int st, int dr, int k) {
if(st >= dr)
return;
int part = partitie (v, st, dr);
int x = part - st + 1;
if(x >= k)
sdo (v, st, part, k);
else
sdo (v, part + 1, dr, k - x);
}
void afisare (int v[]) {
for(int i = 1; i <= n; i ++)
g << v[i] << ' ';
}
int main()
{
f >> n >> k;
for(int i = 1; i <= n; i ++)
f >> v[i];
sdo (v, 1, n, k);
g << v[k];
return 0;
}