Pagini recente » Cod sursa (job #1529596) | Cod sursa (job #773399) | Cod sursa (job #2760353) | Cod sursa (job #406691) | Cod sursa (job #1737538)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> v;
int n,s=0;
int cautbin(int suma, int poz)
{
int st = poz+1, dr = n, m, last = -1;
while(st<=dr)
{
m = (st+dr) / 2;
if(v[m] <= suma)
{
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+1);
for (int i=1; 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(1,n);
for (int i=1; i<n; ++i)
for (int j=i+1; j<=n; ++j)
s+=cautbin(v[i]+v[j],j);
}
int main()
{
read();
solve();
ofstream t ("nrtri.out");
t<<s;
return 0;
}