Cod sursa(job #695257)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 februarie 2012 11:30:21
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#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;
}