Cod sursa(job #3122813)

Utilizator CelestinNegraru Celestin Celestin Data 20 aprilie 2023 18:46:37
Problema Statistici de ordine Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
ifstream f("sdo.in",ios::in);
ofstream g("sdo.out",ios::out);
int v[3000005],n,k;
int partition(int*v,int st,int dr)
{
    int j=st-1,pivot_index=st+rand()%(dr-st+1);
    swap(v[pivot_index],v[dr]);
    for(int i=st;i<dr;i++)
    {
        if(v[i]<=v[pivot_index])
            j++,swap(v[i],v[j]);
    }
    j++;
    swap(v[j],v[pivot_index]);
    return j;
}
void quickselect(int*v,int st,int dr,int k)
{
    if(st<dr)
    {
      int pos=partition(v,st,dr);
      int t=pos-st+1;
      if(t==k)
      {
          g<<v[pos];
          return;
      }
      else{
          if(t<k)
              quickselect(v,pos+1,dr,k);
          else quickselect(v,st,pos-1,k);
      }
    }
}
int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>v[i];
    quickselect(v,1,n,k);
    f.close();
    g.close();
    return 0;
}