Cod sursa(job #1815906)

Utilizator maryan_lupMarian Lupascu maryan_lup Data 25 noiembrie 2016 21:51:04
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#include <time.h>
#define DIMMAX 3000005
#define ll long long

using namespace std;

ll vect[DIMMAX];
ll N, K;

ofstream g("sdo.out");

ll QUICKSORT_SDO(ll inf, ll sup)
{
    ll x, i, j, pivot;
    i = inf;
    j = sup;
    pivot = rand()%((sup-inf+1)+inf);
    x = vect[pivot];
    do
    {
        while ( (i < sup) && (vect[i] < x) ) ++i;
        while ( (j > inf) && (vect[j] > x) ) --j;
        if ( i <= j )
        {
            swap(vect[i], vect[j]);
            i++;
            j--;
        }
    } while ( i <= j );

    if ( K < j ) return QUICKSORT_SDO(inf, j);
    else
        if ( K > j ) return QUICKSORT_SDO(i, sup);
        else
            return vect[j];
}

void citire()
{
    ifstream f("sdo.in");
    f>>N>>K;
    for(ll i=1; i<=N; i++)
        f>>vect[i];
    f.close();
}

int main()
{
    //srand(time(NULL));

    citire();

    g<<QUICKSORT_SDO(1,N);

    g.close();

    return 0;
}