Cod sursa(job #1846067)

Utilizator Walrus21andrei Walrus21 Data 12 ianuarie 2017 09:00:47
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <time.h>
#include <algorithm>
#define N 3000001

using namespace std;

int i, n, k, pk, v[N];

void quicksort(int l, int r)
{
    int i = l, j = r, p = v[l + rand() % (r - l + 1)];
    while(i <= j)
    {
        while(v[i] < p)
            i++;
        while(v[j] > p)
            j--;
        if(i <= j)
        {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }
    if(i - l < pk)
    {
        pk = pk - i + l;
        if(i < r)
            quicksort(i, r);
    }
    else
        if(l < i - 1)
            quicksort(l, i - 1);
}

int main()
{
    freopen("sdo.in", "r", stdin);
    freopen("sdo.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(i = 0; i < n; i++)
        scanf("%d", &v[i]);
    srand(time(NULL));
    pk = k;
    quicksort(0, n - 1);
    printf("%d ", v[k - 1]);
    return 0;
}