Cod sursa(job #1058007)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 14 decembrie 2013 22:32:01
Problema Numarare triunghiuri Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");

int v[2003], n, s;

int bs(int i, int j)
{
	int hi = n, lo = j, val = v[i] + v[j], mid = (hi + lo) / 2;

	/*while(hi - lo>1)
	{
		if(v[mid]<=val && (v[mid + 1]>val || mid+1==n))
			return mid;
		if(v[mid]>=val)
			hi = mid;
		else
			lo = mid;

		mid = (hi + lo)/2;
	}

	if(v[mid]<=val && (v[mid + 1]>val || mid+1==n))
			return mid;
	if(v[hi]<=val && (v[hi + 1]>val || hi+1==n))
			return hi;
	if(v[lo]<=val && (v[lo + 1]>val || lo+1==n))
			return lo;*/
	//varianta 2 (ca pe prima iau 50)
	int n2;
	int pas, sol;
	for ( n2 = 1; 2*n2<=s; n2 *= 2 ){
            }
            sol = j;
            for ( pas = n2; pas>0; pas /= 2 ) {
                if ( sol+pas<n && v[sol+pas]<=val )
                    sol += pas;
            }
			return sol;
}
int main(){
	int player_unu=0;

	in>>n;
	for(int i = 0; i<n; i++)
		in>>v[i];

	sort(v,v+n);

	for(int i = 0; i<n; i++)
	{
		for(int j = i + 1; j<n; j++)
			s += bs(i, j) - j;
	}

	out<<s;

	return player_unu;
}