Cod sursa(job #856176)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 15 ianuarie 2013 23:44:29
Problema Statistici de ordine Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define NMAX 3000004
using namespace std;

ifstream in("sdo.in");
ofstream out("sdo.out");

int V[NMAX],N,K,result ;

int SDO(int start, int final)
{
    if(start == final){ result =  V[start]; return 0;}

    int pivot = V[(start+final)/2],aux,pozitie;
    int left = start, right = final;

    while(left<=right)
    {
        while(V[left]<pivot)
            left++;
        while(V[right]>pivot)
            right--;
        if(left<=right)
        {
            aux = V[left];
            V[left] = V[right];
            V[right] = aux;
            left++,right--;
        }
    }

    for(pozitie=final;pozitie>=start && V[pozitie] !=pivot;pozitie--);
    //vad cate elemente am in stanga
    if(pozitie-start+1 >= K)
        SDO(start,pozitie);
    else K-= (pozitie-start+1),SDO(pozitie+1,final);
}

int main()
{
    int i;
    in>>N>>K;
    for(i=1;i<=N;in>>V[i++]);
    SDO(1,N);
    out<<result<<'\n';
    return 0;
}