Cod sursa(job #2345530)

Utilizator cc4infinityCojocaru Catalin cc4infinity Data 16 februarie 2019 14:17:34
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

int i,j,m,n,a,b,k,t[3000003];

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

int part(int l,int r)
{
    int i=l-1,j=r+1,k=t[l+rand()%(r-l+1)];
    while (1)
    {
        do
        {
            i++;}
        while (t[i]<k);
        do
            {j--;}
        while (t[j]>k);

        if (i<j)
            swap(t[i],t[j]);
          else return j;
    }
}

void srt(int l,int r)
{
    if (l==r) return;
    a=part(l,r);
    if (a>=k)
        srt(l,a);
      else srt(a+1,r);
}

int main()
{
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>t[i];
    srt(1,n);
    fout<<t[k];
    return 0;
}