Trouble

I - Trouble

Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Hassan is in trouble. His mathematics teacher has given him a very difficult problem called 5-sum. Please help him.
The 5-sum problem is defined as follows: Given 5 sets S_1,...,S_5 of n integer numbers each, is there a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0?

 

Input

First line of input contains a single integer N (1≤N≤50). N test-cases follow. First line of each test-case contains a single integer n (1<=n<=200). 5 lines follow each containing n integer numbers in range [-10^15, 1 0^15]. I-th line denotes set S_i for 1<=i<=5.

 

Output

For each test-case output "Yes" (without quotes) if there are a_1 in S_1,...,a_5 in S_5 such that a_1+...+a_5=0, otherwise output "No".

 

Sample Input

2
2
1 -1
1 -1
1 -1
1 -1
1 -1
3
1 2 3
-1 -2 -3
4 5 6
-1 3 2
-4 -10 -1

 

Sample Output

No
Yes

心酸，这道题挖了十多次，一开始是变量写错了，后来又是手抖把=写成+=，然后又是没注意输出格式，要用I64d不能用lld；挖了半天，不会爱，血淋淋的教训
题目思路就是把数据分成2+2+1然后配对，下面贴代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 205;

long long list1[MAXN*MAXN];
long long list2[MAXN*MAXN];
long long list3[MAXN];
long long num[6][MAXN];

int main()
{
    int n,t,cnt;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&t);
        for(int i = 0; i < 5; i++)
        {
            for(int j = 0; j < t; j++)
                scanf("%I64d",&num[i][j]);
        }
        cnt = 0;
        for(int i = 0; i < t; i++)
        {
            for(int j = 0; j < t; j++)
                list1[cnt++] = num[0][i] + num[1][j];
        }
        int l1 = cnt;
        cnt = 0;
        for(int i = 0; i < t; i++)
        {
            for(int j = 0; j < t; j++)
                list2[cnt++] = num[2][i] + num[3][j];
        }
        int l2 = cnt;
        cnt = 0;
        for(int i = 0; i < t; i++)
            list3[cnt++] = num[4][i];
        int l3 = cnt;

        sort(list1,list1 + l1);
        sort(list2,list2 + l2);
        sort(list3,list3 + l3);

        bool have = 0;
        int j,k;



        for(int i = 0; i<l3 && have == 0; i++)
        {
            j = 0, k = l2 -1;
            while(j < l1 && k >= 0)
            {
                if(list1[j] + list2[k] == -list3[i])
                {
                    have = 1;
                    break;
                }
                if(list1[j] + list2[k] > -list3[i])
                {
                    k--;
                }
                else
                {
                    j++;
                }
            }
        }
        if(have)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}