Cod sursa(job #197961)

Utilizator gigi_becaliGigi Becali gigi_becali Data 7 iulie 2008 14:31:10
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
using namespace std;
#define maxh 666013
#define Nmax 1024

FILE*f=fopen("oite.in","r");
FILE*g=fopen("oite.out","w");

struct node
 {
	int i,j;
	node *urm;
 };
node *H[maxh];
int a[Nmax+5],sol;
int S,n;

void read()
{
	fscanf(f,"%d%d",&n,&S);
	int i;
	for(i=1;i<=n;++i) fscanf(f,"%d",&a[i]);
 }

inline void find(int i, int j) //Pt doua oi fixate, caut celelalte oi [cu suma s-a[i]-a[j]].
 {
	int s;
	s=S-a[i]-a[j];
	if(s<=0);
	else
	{
		int h=s%maxh;
		node *q;
		for(q=H[h];q;q=q->urm)
		{
			if(a[q->i]+a[q->j] == s)
			if( q->i==i || q->j==j || q->j==i || q->i==j || i==j || q->i==q->j);
			else
			  {
				   ++sol;
			  }
		}
	}
}

inline void insert(int i, int j)
{
	int h=(a[i]+a[j])%maxh;
	node *p;
	p=new node;
	p->i=i;
	p->j=j;
	p->urm=H[h];
	H[h]=p;
}

void solve()
{
 int i,j;
 for(i=1;i<n;++i)
  for(j=i+1;j<=n;++j)
   insert(i,j);
 for(i=1;i<n;++i)
  for(j=i+1;j<=n;++j)
   {
    find(i,j);
   }
 fprintf(g,"%d\n",sol/6);
 }
int main()
 {
 read();
 solve();
 return 0;
 }