Cod sursa(job #3124569)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 29 aprilie 2023 12:58:43
Problema Statistici de ordine Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 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 pivot_index = right;
    int index = left;

    // cout << a[pivot_index] << '\n';
    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]);

    // for(int i = 1; i <= n; i++)
    //     cout << a[i] << ' ';
    // cout << '\n';

    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;
}