Cod sursa(job #495104)

Utilizator marius21Marius Petcu marius21 Data 23 octombrie 2010 23:53:40
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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;
};


int a[1024];
pnt * v[0x20000];

int hash(int a)
{
	return a&0x1FFFF;
}

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]);
	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;
}