Pagini recente » Cod sursa (job #1289551) | Cod sursa (job #41617) | Cod sursa (job #1012941) | Cod sursa (job #1449689) | Cod sursa (job #793975)
Cod sursa(job #793975)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream ifs("nrtri.in");
ofstream ofs("nrtri.out");
int search(int x);
vector <int> v;
int N;
int result=0;
int main(){
ifs>>N;
v.resize(N);
for(int i=0;i<N;i++)
ifs>>v[i];
sort(v.begin(),v.end());
int top=N;
while(top>=2){
int offset=1;
top--;
while(top>=offset){
int s=search(v[top]-v[top-offset]);
if(s>=top-offset) break;
result+=top-offset-s;
offset++;
}
}
ofs<<result;
return 0;
}
//index of the first element in v that is >=x. Using some crippled binary search.
inline int search(int x){
int min=0,max=N;
int pivot;
while(max>=min){
pivot=(max+min)/2;
if(x>v[pivot])
min=pivot+1;
else if(x<v[pivot])
max=pivot-1;
else
return pivot;
}
return pivot;
}