Problem F : 합이 0이 되는 4개의 숫자들

Problem F : 합이 0이 되는 4개의 숫자들

 

제한시간: 3000 ms    메모리제한: 512 MB

 

 

숫자를 원소로 가지고 있는 A, B, C, D 집합이 있을 때, 

(a, b, c, d ) ∈ A x B x C x D 에 대해 a + b + c + d = 0인 경우의 수가 몇 가지인가 계산하는 프로그램을 작성하라.

여기서 4개의 리스트는 모두 n개의 원소를​ 가지는 집합이라고 가정한다.

 

입력되는 숫자의 크기는 -2​28(268,435,456)<= a, b, c, d <= 2​28(268,435,456) 이하이다.

첫 번째 줄에는 집합의 크기를 나타내는 숫자 n(1≤n≤4,000)이 입력된다. 그 다음 줄부터 n개의 줄에는 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

 

5

-2 2 3 -1

-2 -1 4 2

-2 4 -2 5

-2 2 -4 -2

2 -2 0 4

 

42

 

예제1에서 조건을 만족하는 경우는 다음과 같다.

(-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

 

#include <stdio.h>
#define LN 8 // 4010

const int PLUS = (1 << 29);
const int MOD = (1 << 25);
int N, M, A[LN], B[LN], C[LN], D[LN], bn;

struct data {
	int val, cnt;
	data *next;
	data *myAlloc(int _val, int _cnt, data *_next) {
		val = _val, cnt = _cnt, next = _next;
		return this;
	}
} *hash[MOD], buf[1 << 24];

void push(int key, int val)
{
	for (data *p = hash[key]; p != 0; p = p->next) { 
		if (p->val == val) { // 해시값이 겹치면
			p->cnt++; // 같은 숫자가 있다고 갯수를 입력함
			return;
		}
	}
	hash[key] = buf[bn++].myAlloc(val, 1, hash[key]);
}

int search(int key, int val)
{
	for (data *p = hash[key]; p != 0; p = p->next) {
		if (p->val == val) return p->cnt; // 갯수 만큼 ans에 더함
	}
	return 0;
}

int main()
{
	freopen("input.txt", "r", stdin);
	int i, j, tmp;
	long long ans = 0;
	scanf("%d", &N);
	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++) { // 엔제곱을 두 번 
			tmp = A[i] + B[j] + PLUS; // 2^29을 더해서 겹치지 않도록
			push(tmp % MOD, tmp);
		}
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			tmp = PLUS - C[i] - D[j]; // 위에서 계싼한 값에서 빼서
			ans += search(tmp % MOD, tmp); // 짝을 찾음
		}
	}
	printf("%lld\n", ans);
	return 0;
}

/*
#include <stdio.h>
#define LN 4010
#define key (a[i] >> k) & MOD

const int PLUS = (1 << 29);
const int P = (1 << 8);
const int MOD = P - 1;
int N, M, A[LN], B[LN], C[LN], D[LN], AB[LN * LN], CD[LN * LN], E[LN * LN];

void r_sort(int *a, int *b)
{
int i, k, *tmp, cnt[P];
for (k = 0; k < 32; k += 8) {
for (i = 0; i < P; i++) cnt[i] = 0;
for (i = 0; i < M; i++) cnt[key]++;
for (i = 1; i < P; i++) cnt[i] += cnt[i - 1];
for (i = M - 1; i >= 0; i--) b[--cnt[key]] = a[i];
tmp = a; a = b; b = tmp;
}
}

int main()
{
int i, j, l = 0, r = 0, tmp;
long long ans = 0, cnt1, cnt2;
scanf("%d", &N);
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++) {
AB[M] = A[i] + B[j] + PLUS;
CD[M++] = PLUS - C[i] - D[j];
}
}
r_sort(AB, E);
r_sort(CD, E);
while (l < M && r < M) {
if (AB[l] < CD[r]) l++;
else if (AB[l] > CD[r]) r++;
else {
tmp = AB[l], cnt1 = 0, cnt2 = 0;
while (l < M && AB[l] == tmp) cnt1++, l++;
while (r < M && CD[r] == tmp) cnt2++, r++;
ans += cnt1 * cnt2;
}
}
printf("%lld\n", ans);
return 0;
}
*/