Pagini recente » Cod sursa (job #2099446) | Cod sursa (job #1543502) | Cod sursa (job #1521379) | Cod sursa (job #1239566) | Cod sursa (job #1410128)
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define nmax 3000005
using namespace std;
FILE *fi, *fo;
int n, k;
int A[nmax];
int qs(int st, int dr)
{
int i = st;
int j = dr;
int pivot = A[i + rand() % (j - i + 1)];
while (1)
{
for (; A[i] < pivot;) i++;
for (; A[j] > pivot;) j--;
if (i <= j)
swap(A[i++], A[j--]);
else
return j;
}
return 0;
}
void solve(int st, int dr, int k)
{
if (st == dr)
return;
int pos = qs(st, dr);
int len = pos - st + 1;
if (len >= k)
solve(st, pos, k);
else
solve(pos+1, dr, k-len);
}
int main()
{
fi = fopen("sdo.in", "r");
fo = fopen("sdo.out", "w");
srand(time(0));
fscanf(fi, "%d%d", &n, &k);
for (int i = 1; i <= n; i++)
fscanf(fi, "%d", &A[i]);
solve(1, n, k);
fprintf(fo, "%d", A[k]);
fclose(fi);
fclose(fo);
return 0;
}