Cod sursa(job #1180031)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 29 aprilie 2014 20:30:12
Problema Medie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream in("medie.in");
ofstream out("medie.out");
int v[10000],n;
long long sol;

void quicksort(int left,int right)
{

    int i = left,j = right,aux;
    int pivot = v[(i+j)/2];
    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;
            j--;
            i++;
        }
    }
    if(left < j ) quicksort(left,j);
    if( right > i ) quicksort(i,right);
}

int bin_search(int left,int right,int val)
{
    int mid;
    while(left <= right)
    {

        mid = (left+right)/2;
        if(val >= v[mid]) left = mid+1;
        else right = mid-1;
    }
    return right;
}

int main()
{

    in>>n;
    int i;
    for(i = 1 ; i <= n ; i++)
        in>>v[i];
    quicksort(1,n);
    int j,nr,medie;
    for( i = 1 ; i <= n ; i++)
        for(j = i+1 ; j <= n ; j++)
    {
        medie = (v[j]+v[i])/2;
        if((v[j] + v[i])%2 == 0){
         nr = bin_search(1,n,medie);
         cout<<nr<<"\n";
         if(v[nr] == medie) while(v[nr] == medie) {sol++;nr--;}
        }
    }
    out<<sol;
    return 0;
}