这段代码在spoj中得到了错误的答案 我想要更强大的测试用例来检查我的代码..帮助表示赞赏..
SUM 问题可以表述如下:给定四个整数值列表 A、B、C、D,计算有多少四元组 (a, b, c, d) 属于 A x B x C x D 使得 a + b + c + d = 0 。在下文中,我们假设所有列表具有相同的大小 n
输入
输入文件的第一行包含列表 n 的大小(这个值可以大到 4000)。然后,我们有 n 行包含四个整数值(绝对值与 2^28 一样大),它们分别属于 A、B、C 和 D 。
例子
输入:
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
输出:
5
#include<stdio.h>
#include<stdlib.h>
int binarys(int a,long int b[],int low,int up,int k)
{
int par;
if(low <= up) {
par = partition(low,up,b);
if(b[par] + a == 0) {
k = k + 1;
k = binarys(a,b,low,par-1,k);
k = binarys(a,b,par+1,up,k);
}
if(b[par] > -1*a)
k = binarys(a,b,low,par-1,k);
if(b[par] < -1*a)
k = binarys(a,b,par+1,up,k);
}
return k;
}
int partition(int low,int up,int b[])
{
int i;
int j;
int m;
int a;
j = low - 1;
m = b[up];
for(i=low; i < up; i++) {
if(b[i] <= m ) {
j++;
a = b[i];
b[i] = b[j];
b[j] = a;
}
}
a = b[j+1];
b[j+1] = b[up];
b[up] = a;
return j + 1;
}
int main()
{
long int *A = NULL;
long int *B = NULL;
long int *C = NULL;
long int *D = NULL;
long int *a = NULL;
long int *b = NULL;
int n;
int i;
int j;
int k;
int l;
int sum;
scanf("%d",&n);
k = 0;
sum = 0;
A = (long int*)malloc(n*sizeof(long int));
B = (long int*)malloc(n*sizeof(long int));
C = (long int*)malloc(n*sizeof(long int));
D = (long int*)malloc(n*sizeof(long int));
a = (long int*)malloc(n*n*sizeof(long int));
b = (long int*)malloc(n*n*sizeof(long int));
for(i=0; i < n; i++) {
scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
a[k] = A[i] + B[j];
b[k] = C[i] + D[j];
k++;
}
}
for(i=0; i < n*n; i++) {
l = binarys(a[i],b,0,n*n,0);
sum = sum + l;
}
printf("%d",sum);
return 0;
}