Cod sursa(job #2487819)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 5 noiembrie 2019 19:21:00
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <random>

using namespace std;

int randBetween(int x, int y)
{
    return rand() % (y - x + 1) + x;
}

void printVector(const vector<int> &v)
{
    for(auto x:v)
        cout << x << " ";
    cout << "\n";
}

int kthElement(vector<int> &v, int start, int stop, int k)
{
    int pivot = randBetween(start, stop);
    
    swap(v[pivot], v[stop]);
    int pivotVal = v[stop];
    int smaller = start;
    for(int i = start; i < stop; ++i)
        if(v[i] < pivotVal)
            swap(v[i], v[smaller++]);
    swap(v[smaller], v[stop]);
    
    if(k == smaller)
        return v[k];
    else if(k < smaller)
        return kthElement(v, start, smaller-1, k);
    return kthElement(v, smaller+1, stop, k);
}

int main()
{
    srand((unsigned int)time(0));
    ifstream in("sdo.in");
    int n, k;
    in >> n >> k;
    vector<int> v(n);
    for(int &x:v)
        in >> x;
    in.close();
    
    ofstream out("sdo.out");
    out << kthElement(v, 0, n-1, k-1);
    out.close();
    return 0;
}