Cod sursa(job #1978315)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 7 mai 2017 14:28:59
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

int const nmax = 3000000;

FILE *in = fopen("sdo.in", "r");
FILE *out = fopen("sdo.out", "w");

int v[1 + nmax];

int splitpivot(int* v, int from, int to, int pivot)
{
    int a = from - 1, b = from;
    while(b <= to)
    {
        if(v[b] <= pivot)
        {
            ++ a;
            swap(v[a], v[b]);
        }
        ++ b;
    }
    return a;
}

void search_k(int* v, int from, int to, int k)
{
    if(from == to)
    {
        fprintf(out, "%d", v[from]);
    }
    else
    {
        int pivot = v[rand() % (to - from + 1) + from];
        int med = splitpivot(v, from, to, pivot);
        int ord = med - from + 1;
        if( k <= ord )
        {
            search_k(v, from, med, k);
        }
        else
        {
            search_k(v, med + 1, to, k - ord);
        }
    }
}

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

    int n, k;
    fscanf(in, "%d%d", &n, &k);

    for(int i = 1; i <= n; ++ i)
    {
        fscanf(in, "%d", &v[i]);
    }

    search_k(v, 1, n, k);

    return 0;
}