Cod sursa(job #1310898)

Utilizator nytr0gennytr0gen nytr0gen Data 7 ianuarie 2015 13:43:07
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 3000000;
int v[NMAX];

int nth(int *v, int st, int dr, int k) {
    if (st == dr) return v[st];

    int poz = st + rand() % (dr - st + 1);
    int piv = v[poz],
        i = st, j = dr;
    while (i <= j) {
        while (v[i] < piv) i++;
        while (v[j] > piv) j--;
        if (i <= j) {
            swap(v[i], v[j]);
            i++; j--;
        }
    }

    int t = j - st + 1;
    if (t >= k)
        return nth(v, st, j, k);
    else
        return nth(v, j + 1, dr, k - t);
}

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

    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }

    printf("%d\n", nth(v, 0, n - 1, k));

    return 0;
}