The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

5

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

#include <iostream>
#include   <cstring>
#include   <cstdlib>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include <algorithm>
using namespace std;
const int N=4000+100;
long long  x,v;
int n;
long long  A[N],B[N],C[N],D[N],AB[N*N],CD[N*N];

int main()
{

        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%I64d%I64d%I64d%I64d",&A[i],&B[i],&C[i],&D[i]);
        }
        v=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
               AB[++v]=A[i]+B[j];
            }
        }
        sort(AB+1,AB+v+1);
        v=0;
        long long cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                CD[++v]=C[i]+D[j];
                cnt+=upper_bound(AB+1,AB+n*n+1,-CD[i])-lower_bound(AB+1,AB+n*n+1,-CD[i]);
            }
        }
        cout << cnt << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

超时ing

#include <iostream>
#include   <cstring>
#include   <cstdlib>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include <algorithm>
using namespace std;
const int N=4000+100;
long long  x,v;
int n;
long long  A[N],B[N],C[N],D[N],AB[N*N],CD[N*N];
long long sreach(long long  k){
    long long  l=1;
    long long  r=n*n;

    while(l<=r){
        long long  mid=(l+r)/2;
        if(AB[mid]==k){
            long long   ans=1;
            long long  temp=mid+1;
            while(AB[temp]==k&&temp<=n*n){
                temp++;
                ans++;
            }
            temp=mid-1;
            while(AB[temp]==k&&temp>=1){
                temp--;
                ans++;
            }
            return ans;
        }
        else if(AB[mid]<k)
            l=mid+1;
        else
            r=mid-1;
    }
    return 0;
}
int main()
{
    //int t=0;
    //while(scanf("%d",&n)!=EOF){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%I64d%I64d%I64d%I64d",&A[i],&B[i],&C[i],&D[i]);
        }
        v=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
               AB[++v]=A[i]+B[j];
            }
        }
        sort(AB+1,AB+v+1);
        v=0;
        long long cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                CD[++v]=C[i]+D[j];
                //cnt+=upper_bound(AB+1,AB+n*n+1,-CD[i])-lower_bound(AB+1,AB+n*n+1,-CD[i]);
                cnt+=sreach(-CD[v]);
            }
        }
        cout << cnt << endl;
    //}
    //cout << "Hello world!" << endl;
    return 0;
}

在删减各种东西以后掐着时间过。。。。

#include <iostream>
#include   <cstring>
#include   <cstdlib>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include <algorithm>
using namespace std;
const int N=4000+100;
int n,v;
int  A[N],B[N],C[N],D[N];
long long AB[N*N];
long long sreach(long long  k){
    long long  l=1;
    long long  r=n*n;
    long long   ans,temp;
    while(l<=r){
        long long  mid=(l+r)/2;
        if(AB[mid]==k){
            ans=1;
            temp=mid+1;
            while(AB[temp]==k&&temp<=n*n){
                temp++;
                ans++;
            }
            temp=mid-1;
            while(AB[temp]==k&&temp>=1){
                temp--;
                ans++;
            }
            return ans;
        }
        else if(AB[mid]<k)
            l=mid+1;
        else
            r=mid-1;
    }
    return 0;
}
int main()
{
    //int t=0;
    //while(scanf("%d",&n)!=EOF){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
        }
        v=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
               AB[++v]=A[i]+B[j];
            }
        }
        sort(AB+1,AB+v+1);
        long long cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                //cnt+=upper_bound(AB+1,AB+n*n+1,-CD[i])-lower_bound(AB+1,AB+n*n+1,-CD[i]);
                cnt+=sreach(-C[i]-D[j]);
            }
        }
        cout << cnt << endl;
    //}
    //cout << "Hello world!" << endl;
    return 0;
}