Cod sursa(job #2835450)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 18 ianuarie 2022 19:08:42
Problema Statistici de ordine Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
mt19937 rng(time(NULL));
int n,k,v[3000005];
int quickselect(int l,int r,int k)
{
    if(l==r)
        return v[l];
    int lg=r-l+1;
    int p=v[(l+r)/2];
    int b=l,e=r;
    while(b<=r&&v[b]<p)
        b++;
    while(e>=l&&v[e]>p)
        e--;
    while(b<e)
    {
        swap(v[b],v[e]);
        while(b<=r&&v[b]<p)
            b++;
        while(e>=l&&v[e]>p)
            e--;
    }
    if(k<=b)
        return quickselect(l,b,k);
    else
        return quickselect(b+1,r,k);
}
int main()
{
    string s;
    fin>>n>>k;
    fin.get();
    getline(fin,s);
    int nr=0;
    int poz=0;
    for(int i=1;i<=n;i++)
    {
        nr=0;
        while(poz<s.size()&&isdigit(s[poz]))
        {
            nr=nr*10+s[poz]-'0';
            poz++;
        }
        poz++;
        v[i]=nr;
    }
    fout<<quickselect(1,n,k);
    return 0;
}