Cod sursa(job #1625511)

Utilizator Tzappy90Mihalache Constantin Tzappy90 Data 2 martie 2016 19:27:40
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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 pivot = v[upper];
    uint i = lower;
    for (uint j = lower; j < upper; j++) {
        if (v[j] <= pivot) {
            swap(&v[j], &v[i++]);
        }
    }
    swap(&v[i], &v[upper]);
    return i;
}

uint find_kth_min(std::vector<uint> &v, uint lower, uint upper, uint k) {
    int p = partition(v, lower, upper);
    if (p == k) {
        return v[k];
    }

    if (p < k) {
        return find_kth_min(v, p + 1, upper, k);
    }
    return find_kth_min(v, lower, p - 1, k);
}

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

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

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