Cod sursa(job #197964)

Utilizator gigi_becaliGigi Becali gigi_becali Data 7 iulie 2008 14:37:19
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
using namespace std;
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#define r 17
const int maxn =666714;
const int mod=566703;
#define ui unsigned int
struct nod { short i, j; int sum;nod *next;};//__attribute__((packed));

nod *H[maxn];
short n;
ui S;
ui x[1024];
ui nr;
inline void insert(short i, short j)
{
	nod *t=new nod;
	t->i=i; t->j=j;
	t->sum=x[i]+x[j];
	ui h=((t->sum))%mod;
	t->next=H[h];
	H[h]=t;
}

inline int find(short i, short j)
{
	ui  sum=S-(x[i]+x[j]);
	nod *t;
	ui h=((sum))%mod;
	for(t=H[h];t;t=t->next)
		if(t->sum==sum)
		
			if(t->i==i || t->i==j || t->j==i || t->j==j);
			else //{ printf("%d %d %d %d\n",i, j, t->i, t->j);++nr;}
			++nr;
		
	return nr;
}

int main()
{
	freopen("oite.in","r",stdin);
	scanf("%d %d\n", &n, &S);
	short i, j;
	//	init();
	nod *t, *p;
	ui h;
	for(i=1;i<=n;++i) scanf("%d ", x+i);
	sort(x+1, x+n+1);
	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
		
			/*
			h=t->sum-(t->sum/mod)*mod;
			for(p=H[h];p;p=p->next)
				if(p->sum==sum)
				{
					++p->val;
					
				}
			t=new nod;
			t->i=i; t->j=j;
			t->sum=x[i]+x[j];
		
			//h=((t->sum))%mod;
			
			t->next=H[h];
			H[h]=t;
			*/
		
			insert(i,j);
		
	

	ui sum;
	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
		{
			sum=S-(x[i]+x[j]);
			
			//h=((sum))%mod;
			h=sum-(sum/mod)*mod;
			for(t=H[h];t;t=t->next)
			if(t->sum==sum)
		
			if(t->i==i || t->i==j || t->j==i || t->j==j);
			else //{ printf("%d %d %d %d\n",i, j, t->i, t->j);++nr;}
			++nr;
			
		}
		
		//	find(i, j);
		
	freopen("oite.out","w",stdout);
	printf("%d\n", nr/6);
	return 0;
}