SPOJ ABCDEF Solution

| July 01, 2015

The correct, optimal and working solution for programming question ABCDEF on spoj

#include <cstdio>
#include <algorithm>

using namespace std;

void readInt(int &n){
    int sign = 1;
    char c;
    bool found = false;
    n = 0;
    
    while(true){
    	c = getc(stdin);
    	
        switch(c){
            case '-' :
                sign = -1;
                found = true;
                break;
            case ' ':
                if(found) goto jump;
                break;
            case '\n':
                if(found) goto jump;
                break;
            default:
                if(c>='0' && c<='9'){
                    n = n*10+c-'0';
                    found = true;
                }else goto jump;
                break;
        }
    }
    
    jump:
        n *= sign;
}

int szB,szC,contB[1000000],contC[1000000];
int B[1000000],C[1000000];

int main(){
    int N;
    readInt(N);
    
    int A[N];
    
    for(int i = 0;i<N;++i)
        readInt(A[i]);
    
    szB = szC = 0;
    
    for(int a = 0;a<N;++a)
        for(int b = 0;b<N;++b)
            for(int c = 0;c<N;++c)
                B[szB++] = A[a]*A[b]+A[c];
    
    for(int d = 0;d<N;++d)
        if(A[d]!=0)
            for(int e = 0;e<N;++e)
                for(int f = 0;f<N;++f)
                    C[szC++] = A[d]*(A[e]+A[f]);
    
    sort(B,B+szB);
    sort(C,C+szC);
    
    int n = 1,m = 1;
    contB[0] = contC[0] = 1;
    
    for(int i = 1;i<szB;++i){
        if(B[i]!=B[n-1]){
            B[n] = B[i];
            contB[n] = 1;
            ++n;
        }else ++contB[n-1];
    }
    
    for(int i = 1;i<szC;++i){
        if(C[i]!=C[m-1]){
            C[m] = C[i];
            contC[m] = 1;
            ++m;
        }else ++contC[m-1];
    }
    
    long long ans = 0;
    
    for(int i = 0,j = 0;i<n && j<m;){
        if(B[i]==C[j]) ans += (long long)contB[i]*contC[j];
        
        if(B[i]>C[j]) ++j;
        else if(B[i]<C[j]) ++i;
        else{
            ++i;
            ++j;
        }
    }
    
    printf("%lld\n",ans);
    
    return 0;
}