Cod sursa(job #1559495)

Utilizator aetherAlexandra Vanca aether Data 30 decembrie 2015 22:20:18
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
# include <iostream>
# include <fstream>
# include <cstdlib>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int n, v[3000001], k;
int solve(int left, int right, int k)
{
    if (left==right)
        return v[left];
    int pivot=v[rand()%(right-left+1)+left+1], i=left, j=right, aux;
    while (i<=j)
    {
        while (v[i]<pivot)
            i++;
        while (v[j]>pivot)
            j--;
        if (i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
    }
    aux=j-left+1;
    if (aux>=k)
        return solve(left, j, k);
    else
        return solve(j+1, right, k-aux);
}

int main()
{
    f>>n>>k;
    int i;
    for (i=1; i<=n; i++)
        f>>v[i];
    g<<solve(1, n, k);
    f.close();
    g.close();
}