Cod sursa(job #1020640)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 2 noiembrie 2013 13:54:56
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include  <fstream>
#include <ctime>
#include <cstdlib>
int k,a[3000000];
using namespace std;
ifstream h("sdo.in");
ofstream g("sdo.out");

void quicksort(int *a,int f,int n)
{
    int p,j,aux,i,p1,p2,p3;
    if(f<n)
    {
        srand((unsigned int)time(NULL));
        p1=rand() % (n-f+1) +f;
        p2=rand() % (n-f+1) +f;
        p3=rand() % (n-f+1) +f;
        p=f;
        if ((p2<=p1 && p1<=p3) || (p3<=p1 && p1<=p2)) p=p1;
        if ((p1<=p2 && p2<=p3) || (p3<=p2 && p2<=p1)) p=p2;
        if ((p1<=p3 && p3<=p2) || (p2<=p3 && p3<=p1)) p=p3;
        
        i=f;
        j=n;
        
        while(i<j){
            while(a[i]<=a[p]&&i<n)
                i++;
            while(a[j]>a[p])
                j--;
            if(i<j){
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
        }
        
        aux=a[p];
        a[p]=a[j];
        a[j]=aux;
        if (k==j){ g<<a[j]; return;}
        else if (j<k) quicksort(a,j+1,n);
        else quicksort(a,f,j-1);
        
    }
    else g<<a[f];
    return;
}



int main()
{int n,i;
    h>>n>>k;
    for (i=1;i<=n;i++) h>>a[i];
    quicksort(a,1,n);
    h.close();
    g.close();
    return 0;
}