Pagini recente » Cod sursa (job #2416203) | Cod sursa (job #2588993) | Cod sursa (job #1846654) | Cod sursa (job #2715799) | Cod sursa (job #695257)
Cod sursa(job #695257)
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include<algorithm>
using namespace std;
const int N = 3000005;
int a[N], n, k;
char s[N * 10];
inline bool cifra(char c) {
if (c >= '0' && c <= '9')
return true;
return false;
}
void citire() {
scanf("%d%d\n", &n, &k);
gets(s);
int x = 0, poz = 0;
for (int i = 0; s[i]; ++i) {
if (cifra(s[i]))
x = x * 10 + (s[i] - '0');
else {
a[++poz] = x;
x = 0;
}
}
a[++poz] = x;
}
int prelucrare(int left, int right) {
int st = left, dr = right, pivot = a[left + (rand() % (right - left + 1) )];
while(true) {
while (st <= right && a[st] < pivot)
++st;
while (dr >= left && a[dr] > pivot)
--dr;
if (st < dr)
swap(a[st], a[dr]);
else
return dr;
}
return 0;
}
void quicksort(int left, int right, int k) {
if(left == right)
return;
int poz = prelucrare(left, right);
int p = poz - left + 1;
if (p >= k)
quicksort(left, poz, k);
else
quicksort(poz + 1, right, k - p);
}
int main() {
freopen("sdo.in", "r", stdin);
freopen("sdo.out", "w", stdout);
srand(time(0));
citire();
quicksort(1, n, k);
printf("%d\n", a[k]);
return 0;
}