1152 - 4 Values whose Sum is 0

[Shihab]

help tle

Code: Select all

#include <cmath>
#include <climits>

#include <queue>

#include <vector>

#include <map>

#include <cstdlib>

#include <fstream>

#include <iomanip>

#include <iostream>

#include <sstream>  // istringstream buffer(myString);

#include <stack>

#include <algorithm>

#include <cstring>

#include <cassert>

using namespace std;

map<int,int>map1;
//int half1[16000001],half2[16000001];
int i = 1;
int k,j;
int n;
int a[4][4000];
int tc;

int main()
{

    //freopen("in.txt","r",stdin );
    //freopen("out.txt","w+",stdout );

    scanf("%d",&tc);

    for( i=1; i<=tc; i++ )
    {

        scanf("%d",&n);

        map1.clear();

        int c1 = 0;

        for( j=1; j<=n; j++)
        {
            scanf("%d %d %d %d",&a[0][j],&a[1][j],&a[2][j],&a[3][j]);
        }

        int g=0;
        for( k=1; k<=n; k++ )
        {
            for( j=1; j<=n; j++ )
            {
                map1[ a[0][k] + a[1][j] ]++;
            }
        }

        g = 0;

        for( k=1; k<=n; k++ )
        {
            for( j=1; j<=n; j++ )
            {
                if( map1[(a[2][k] + a[3][j]) *-1 ] )
                {
                    map1[(a[2][k] + a[3][j]) *-1 ]--;
                    c1++;
                }
            }
        }


        if( i!=1 )
            printf("\n");
        printf("%d\n",c1);

    }

    return 0;
}

[brianfry713]

Try solving it with an array instead of STL map.
Compute half1 as the sum of each a and each b. Sort half1, and then create a new sorted map-like array with two elements: each number in half1 and the number of times it occurs in half1.
For each c plus each d, do a binary search of the map-like array to search for that sum.

Part of your algorithm is also wrong.
Input:

Code: Select all

1

2
0 1 0 -1
1 0 -1 0

AC output 6