Pagini recente » Cod sursa (job #2531492) | Cod sursa (job #2104083) | Cod sursa (job #1184843) | Cod sursa (job #1643379) | Cod sursa (job #1737536)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int n,s=0;
int bin_search(int x,int poz)
{int st = poz+1, dr = n, m, last = -1;
while(st<=dr)
{
m = (st+dr) / 2;
if(v[m] <= x)
{
last = m;
st = m + 1;
}
else
{
dr = m - 1;
}
}
if(last!= - 1) return last - poz;
else return 0;
}
void read()
{
ifstream f ("nrtri.in");
f>>n;
v.resize(n);
for (int i=0; i<n; ++i)
f>>v[i];
}
int partition(int low,int high)
{
int mid=(low+high)/2,pivot=v[mid],i=low-1,j=high+1;
LOOP:
do ++i;
while (v[i]<pivot);
do --j;
while (v[j]>pivot);
if (i>=j)
return j;
swap(v[i],v[j]);
goto LOOP;
}
void quicksort(int low,int high)
{
if (low<high)
{
int pivot=partition(low,high);
quicksort(low,pivot);
quicksort(pivot+1,high);
}
}
void solve()
{
sort(v.begin(),v.end());
for (int i=0; i<n-1; ++i)
for (int j=i+1; j<n; ++j)
s+=bin_search(v[i]+v[j],j);
}
int main()
{
read();
solve();
ofstream t ("nrtri.out");
t<<s;
return 0;
}