Cod sursa(job #2621800)

Utilizator ValentinBaluIonut Valentin Balu ValentinBalu Data 30 mai 2020 19:38:59
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int l,n,i,v[3000001];

int separare(int st,int dr,int v[]){
    int pivot=dr,i=st,j;
    for(j=st;j<dr;j++) //cautam pozitia pivotului
        if(v[j]<v[pivot]){
            swap(v[i],v[j]);
            i++;
        }
    swap(v[pivot],v[i]);
    return i;
}

int def_pivot(int st,int dr,int v[]){
    int pivot,r;
    r=rand();
    pivot=st+r%(dr-st+1); //alegem pivotul random
    swap(v[dr],v[pivot]);
    return separare(st,dr,v);
}

int quick(int st,int dr,int v[],int val){//alg asemanator cu quick sort dar se ocupa de anumite portiuni ce ajuta la determinarea solutiei
    int i,poz;
    if(st==dr)
        return v[st];
    i=def_pivot(st,dr,v); //definim pivotul random
    poz=i-st+1;
    if(val<=poz) //ne orientam doar pe portiunea ce contine valoarea
        quick(st,i,v,val);
    else
        quick(i+1,dr,v,val-poz);
}

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