Cod sursa(job #224469)

Utilizator ProtomanAndrei Purice Protoman Data 29 noiembrie 2008 23:38:09
Problema Oite Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define mx 1030
#define bz_hash 870000

using namespace std;

struct poz
{
	short e1, e2;
	poz *ua;
} *hash[bz_hash + 4];
int n, l, nr;
int a[mx];
long long rez;
double A;

void coh(long loc, short p1, short p2)
{
	poz *p = new poz;
	p->e1 = p1;
	p->e2 = p2;
	p->ua = hash[loc];
	hash[loc] = p;
}

void ver(long loc, short p1, short p2)
{
	for (poz *p = hash[loc]; p; p = p->ua)
		if ((p1 != p->e1) && (p2 != p->e1) && (p1 != p->e2) && (p2 != p->e2))
			if (a[p1] + a[p2] + a[p->e1] + a[p->e2] == l)
				rez++;
}

int main()
{
	double A = (sqrt((double) 5) - 1) / 2;
	freopen("oite.in","r",stdin);
	freopen("oite.out","w",stdout);
	scanf("%d %d", &n, &l);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			int sp = a[i] + a[j];
			double gs = sp * A - (int) (sp * A);
			int loc = (double) gs * bz_hash;
			coh(loc, i, j);
		}
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
			if (l > a[i] + a[j])
			{
				int sp = l - (a[i] + a[j]);
				double gs = sp * A - (int) (sp * A);
				int loc = (double) gs * bz_hash;
				ver(loc, i, j);
			}
	printf("%lld\n", rez / 6);
	fclose(stdin);
	fclose(stdout);
	return 0;
}