Cod sursa(job #3124525)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 29 aprilie 2023 11:31:39
Problema Statistici de ordine Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <algorithm>
#include <cassert>
#include <queue>
#include <cstdlib>
#define ll long long

using namespace std;

ifstream cin("sdo.in");
ofstream cout("sdo.out");

const int NMAX = 3e6;
int n, k;
int a[NMAX + 1];

int QuickSelect(int left, int right)
{
    int pivot_index = rand() % (right - left + 1) + left;
    int index = left;

    for(int i = left; i <= right; i++)
        if(i != pivot_index && a[i] <= a[pivot_index])
            swap(a[index++], a[i]);

    swap(a[index], a[pivot_index]);

    if(index < k)
        return QuickSelect(index + 1, right);

    if(index > k)
        return QuickSelect(left, index - 1);

    return a[index];
}

int main()
{
    srand(time(NULL));
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    cout << QuickSelect(1, n);

    return 0;
}