Cod sursa(job #1625479)

Utilizator Tzappy90Mihalache Constantin Tzappy90 Data 2 martie 2016 19:15:37
Problema Statistici de ordine Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>

typedef unsigned int uint;

void swap(uint *a, uint *b) {
    if (*a == *b) {
        return;
    }
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

int partition(std::vector<uint> &v, uint lower, uint upper) {
    uint pivotIndex = lower + (upper - lower) / 2;
    uint pivot = v[pivotIndex];

    swap(&v[pivotIndex], &v[upper]);
    uint store = lower;
    uint i = upper - 1;
    while (i > store) {
        while (i > store && v[store] <= pivot)
            store++;
        while (i > store && v[i] > pivot)
            i--;
        if (i > store)
            swap(&v[i], &v[store]);
    }
    if (v[store] > v[upper]) {
        swap(&v[upper], &v[store]);
    }
    return store;
}

uint find_kth_min(std::vector<uint> &v, uint lower, uint upper, uint k) {
    uint begin = lower, end = upper;

    int p = partition(v, begin, end);
    if (p != k) {
        if (p < k) {
            return find_kth_min(v, p + 1, upper, k);
        } else {
            return find_kth_min(v, lower, p - 1, k);
        }
    }

    return v[k];
}

int main(void) {
    std::ifstream f("sdo.in");
    std::ofstream g("sdo.out");
    uint n, x;
    f >> n >> x;
    std::vector<uint> v(n);
    for (uint i = 0; i < n; f >> v[i++]);

    g << find_kth_min(v, 0, v.size() - 1, x - 1) << '\n';

    g.close();
    f.close();
}