Cod sursa(job #480665)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 29 august 2010 02:33:27
Problema Oite Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include<list>
#include <iostream>

#define NMAX 1026
#define h 699967

using namespace std;

int A[NMAX];
int NR;
int S,N;

list< pair<int,int> > List[h+2];

inline int hash(int x)
{
	return x%h;
}


void rezolva()
{
	int x,z;
	for(int i=1;i<=N-3;i++)
		for(int j=i+1;j<=N-2;j++)
		{
			x=S-(A[i]+A[j]);
			if(x>0)
			{
				z=hash(x);
				if(!List[z].empty())
					for(list<pair<int,int> >::iterator itr=List[z].begin();itr!=List[z].end();++itr)
					{
						if(itr->first == x && j<itr->second / 10000)
						{
							if(itr->second / 10000 != i && itr->second % 10000 != i)
								if(itr->second / 10000 != j && itr->second %10000 !=j)
								{
									NR++;
//									cout<<itr->first<<" "<<x<<" "<<itr->second<<" "<<i<<" "<<j<<endl;
								}
						}
					}
			}
		}
}

void init()
{
	for(int i=3;i<=N-1;i++)
		for(int j=i+1;j<=N;j++)
		{
			List[hash(A[i]+A[j])].push_back(make_pair(A[i]+A[j],i*10000+j));
		}
}

void citire()
{
	fstream fin("oite.in",ios::in);
	
	fin>>N>>S;
	
	for(register int i=1;i<=N;i++)
		fin>>A[i];
	
	fin.close();
}

void afisare()
{
	fstream fout("oite.out",ios::out);
	
	fout<<NR<<"\n";
	
	fout.close();
}

int main(int argc, char* argv[])
{
	citire();
	
	init();
	
	rezolva();
	
	afisare();
}