Cod sursa(job #1100849)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 7 februarie 2014 16:03:20
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>

#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX_N = 3000002;

int N, K, sol;
int v[MAX_N];

void quicksort(int l, int r, int k) {
    if(l == r)
        sol = v[l];
    else {
        int pivot = v[l + (rand() % (r - l + 1))], i = l, j = r;

        while(i <= j) {
            while(v[i] < pivot)
                ++i;
            while(v[j] > pivot)
                --j;
            if(i <= j) {
                swap(v[i], v[j]);
                ++i, --j;
            }
        }

        if(k <= j - l + 1)
            quicksort(l, j, k);
        else quicksort(j + 1, r, k - j + l - 1);
    }
}

int main() {
    freopen("sdo.in", "r", stdin);
    freopen("sdo.out", "w", stdout);

    srand(time(NULL));

    scanf("%d %d", &N, &K);
    for(int i = 1; i <= N; ++i)
        scanf("%d", &v[i]);

    quicksort(1, N, K);

    printf("%d\n", sol);

    return 0;
}