Cod sursa(job #495114)

Utilizator marius21Marius Petcu marius21 Data 24 octombrie 2010 00:05:01
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstdlib>
#include <list>

using namespace std;

FILE *fin=fopen("oite.in","r");
FILE *fout=fopen("oite.out","w");

struct pnt {
	int x,y;
	pnt * next;
};

#define max 0x100000

int a[1024];
pnt * v[max];

int hash(int a)
{
	return a&(max-1);
}

int main (int argc, char * const argv[]) {
	int n,l;
	fscanf(fin, "%d%d",&n,&l);
	for (int i=0; i<n; i++)
		fscanf(fin, "%d",&a[i]);
	memset(v, 0, sizeof(void*)*max);
	for (int i=0; i<n; i++)
		for (int j=i+1; j<n; j++)
		{
			pnt * tmp = new pnt;
			tmp->x= i;
			tmp->y= j;
			int hs = hash(a[i]+a[j]);
			tmp->next=v[hs];
			v[hs] = tmp;
		}
	int sum = 0;
	for (int i=0; i<n; i++)
		for (int j=i+1; j<n; j++)
		{
			for (pnt * ii = v[hash(l-a[i]-a[j])]; ii!=NULL; ii=ii->next)
			{
				if (j>=ii->x) continue;
				if ((a[ii->x]+a[ii->y])!=(l-a[i]-a[j])) continue;
				sum++;
			}
		}
	fprintf(fout, "%d",sum);
	fclose(fin);
	fclose(fout);
    return 0;
}