Cod sursa(job #72991)

Utilizator gigi_becaliGigi Becali gigi_becali Data 16 iulie 2007 09:26:49
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
using namespace std;
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#define r 17
const int maxn =206713;
const int mod=566703;
#define ui unsigned int
struct nod { short i, j;}__attribute__((packed));

nod *H[maxn+1];
int len[maxn+1];
short n;
ui S;
ui x[1024];
ui nr;
inline void insert(short i, short j)
{
	nod t;
	t.i=i; t.j=j;
	
	ui h=((x[i]+x[j]))%maxn;
	//H[h]=(nod*) realloc(H[h], sizeof(nod)*(len[h]+2));
	H[h][len[h]++]=t;
//	t->next=H[h];
	//H[h]=t;
}

inline void find(short i, short j)
{
	ui  sum=S-(x[i]+x[j]);
	ui h=((sum))%maxn;
	ui ii, jj;
	nod *p;
	int t;
//	for(int t=len[h]-1;t>=0;--t)
	for(p=H[h], t=len[h]-1;t>=0;++p, --t)
	{
		ii=p->i;//H[h][t].i;
		jj=p->j;//H[h][t].j;
		if(x[ii]+x[jj]==sum)
			if(ii==i || ii==j || jj==i || jj==j);
			else ++nr;
	}
	/*
	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;
		
	*/

}
inline void rad(int byte, int n, ui a[], ui b[])
{
	int count[256], index[256];
	memset(count, 0, sizeof(count));
	int i;
	for(i=1;i<=n;++i) ++count[(a[i]>>byte)&0xff];
	index[0]=1;
	for(i=1;i<256;++i) index[i]=index[i-1]+count[i-1];
	for(i=1;i<=n;++i) b[index[(a[i]>>byte)&0xff]++]=a[i];
}


inline void radix(int n)
{
	ui b[maxn];
	
	rad(0, n, x, b);
	rad(8, n, b, x);
	rad(16,n, x, b);
	rad(24,n, b,x);
}

int main()
{
	freopen("oite.in","r",stdin);
	scanf("%d %d\n", &n, &S);
	short i, j;
	//	init();
	
	ui h;
	for(i=1;i<=n;++i) scanf("%d ", x+i);
	//sort(x+1, x+n+1);
	radix(n);
	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
		{
			h=(x[i]+x[j])%maxn;
			++len[h];
		}
		
	for(int i=0;i<maxn;++i)
		H[i]=(nod*)malloc(sizeof(nod)*(len[i]));;

	memset(len, 0, sizeof(len));

	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
			insert(i,j);
		
	

	ui sum;
	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
			find(i, j);
		

	freopen("oite.out","w",stdout);
	printf("%d\n", nr/6);
	return 0;
}