Cod sursa(job #122150)

Utilizator TabaraTabara Mihai Tabara Data 10 ianuarie 2008 23:05:36
Problema Medie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>

#define in "medie.in"
#define out "medie.out"
#define NMAX 9005

int V[NMAX];
int n, VAL, nrsol, FIND;

void QSort(int,int);
int BS( int X, int _init, int _final, int P);

int main()
{
    freopen( in, "r", stdin );
    freopen ( out, "w", stdout );
    
    scanf( "%d", &n );
    int i,j;
    for ( i = 1; i <= n; ++i )
        scanf( "%d", &V[i] );
        
    QSort( 1, n );
    
    for ( i = 1; i <= n; ++i )
    {
        VAL = (V[i]<<1);
        for ( j = 1; j <= n; ++j )
        {
            if ( i == j ) continue;
            FIND = VAL - V[j];
            nrsol += BS( FIND, j+1, n, i);
        }
    }
    
    printf( "%d\n", nrsol );           
    return 0;
}

int BS( int X, int _init, int _final, int P)
{
   bool ok = false;
   bool ok2 = false;
   int poz1, poz2, count, st, dr, mij;
   st = _init, dr = _final;
      
   while ( st <= dr )
   {
         mij = ((st+dr)>>1);
         if ( X < V[mij] ) dr = mij-1;
         else if ( X > V[mij] ) st = mij+1;
         else if ( X == V[mij] ) 
         {
              ok = true, poz2 = mij, st = mij+1;//ultima poz din sir 
              if ( mij == P ) ok2 = true;
         }
   }
   st = _init, dr = _final;//optimizare aici ar merge!!! ( pornesc din st si dr aflatia anterior )
   
   if ( !ok ) return 0;
   
   while ( st <= dr )
   {
         mij = ((st+dr)>>1);
         if ( X < V[mij] ) dr = mij-1;
         else if ( X > V[mij] ) st = mij+1;
         else if ( X == V[mij] ) 
         {
              poz1 = mij, dr = mij-1;//prima poz din sir
              if ( mij == P ) ok2 = true;//nu-s asa sigur pe asta
         }
   }
   
   if ( !ok ) return 0;
   else 
   {    
        if ( ok2 == true ) return poz2-poz1;
        else return poz2-poz1+1;
   }
}

void QSort( int st, int dr )
{
     int i = st-1, j = dr+1;
     int pivot = V[st];
     do
     {
         do { i++; } while ( V[i] < pivot ); 
         do { j--; } while ( V[j] > pivot );
         if ( i <= j )
         {
              int aux = V[i];
              V[i] = V[j];
              V[j] = aux;
         }
     } while ( i <= j );
     if ( i < dr ) QSort( i, dr );
     if ( st < j ) QSort( st, j );
}