Pagini recente » Cod sursa (job #730890) | Cod sursa (job #1757766) | Cod sursa (job #537842) | Cod sursa (job #712477) | Cod sursa (job #1737520)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> v;
int n,s=0;
int bin_search_low(int x)
{
int i = 0, pas = (1 << 16);
while (pas != 0)
{
if (i + pas <= n && v[i + pas] <= x)
i += pas;
pas /= 2;
}
if (v[i]!=x) --i;
if (i-1<=0) return 0;
else
return i-1;
}
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()
{
quicksort(0,n-1);
for (int i=0; i<n-2; ++i)
for (int j=i+1; j<n-1; ++j)
s+=bin_search_low(v[i]+v[j]);
}
int main()
{
read();
solve();
ofstream t ("nrtri.out");
t<<s;
return 0;
}