Cod sursa(job #2780406)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 6 octombrie 2021 22:39:18
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define NMAX 3000001

using namespace std;

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

int n,k;
int v[NMAX];

int solve(int st, int dr, int cnt)
{
    if(st==dr)
        return v[st];
    int pivot=v[st + rand()%(dr-st+1)];
    int i=st-1,j=dr+1;
    while(true)
    {
        do
        {
            ++i;
        }while(v[i]<pivot);
        do
        {
            --j;
        }while(pivot<v[j]);
        if(i<j)
            swap(v[i],v[j]);
        else
        {
            if(i-st>=cnt)
                return solve(st,i-1,cnt);
            else
                return solve(i,dr,cnt-i+st);
        }
    }
}

int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++)
        in>>v[i];
    out<<solve(1,n,k);
    return 0;
}