Cod sursa(job #2622427)

Utilizator ihorvaldsTudor Croitoru ihorvalds Data 1 iunie 2020 12:11:15
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <iostream>
#include <algorithm>

int pivot(int start, int end) {
    return start + rand() % (end - start + 1);
}

int quick(int * v, int start, int end, int pos) {
    if (start == end) {
        return v[start];
    }

    int p = pivot(start, end);
    std::swap(v[p], v[end]);
    p = end;
    int b, c;
    b = c = start;
    for (; b < end; b++) {
        if (v[b] < v[p]) {
            std::swap(v[b], v[c]);
            c++;
        }
    }
    std::swap(v[p], v[c]);

    int m = c - start;

    if (pos <= m) {
        return quick(v, start, c, pos);
    } else {
        return quick(v, c + 1, end, pos - m - 1);
    }
}

int main() {
    std::ifstream f("sdo.in");
    std::ofstream g("sdo.out");

    int n, i;
    f >> n >> i;

    int* a = new int[n] {0};
    int j = 0;
    for (j = 0; j < n; j++) {
        f >> a[j];
    }

    g << quick(a, 0, n-1, i - 1) << "\n";
    delete[] a;
}