Cod sursa(job #348437)

Utilizator serbanlupulupulescu serban serbanlupu Data 15 septembrie 2009 19:45:47
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
//infoarena

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
	short left, right;
	node(short i, short j) {left=i; right=j; }
};
#define PRIM 666203

vector<node > H[PRIM+1];

int v[1050];
short nr_v;
int L;

void read()
{
	fstream f("oite.in", ios::in);
	f>>nr_v;
	f>>L;
	for (short i=1; i<=nr_v; ++i)
		f>>v[i];
	f.close();
	sort(v+1, v+nr_v+1);
}

int numar;

void check(int sum, short i, short j)
{		
	vector<node >::iterator it;
	for (it=H[sum%PRIM].begin(); it<H[sum%PRIM].end(); it++)
		if ( (v[it->left]+v[it->right]) == sum )
			if (it->right < i)
				++numar;
}

struct cmp
{
	bool operator() (const node &aux, const node &aux1) const 
	{
		if ( (v[aux.left]+v[aux.right]) < (v[aux1.left]+v[aux1.right]) )
			return 1;
		else
			return 0;
	}
};

void solve()
{
	for (short i=1; i<nr_v; ++i)
		for (short j=i+1; j<=nr_v; ++j)
		{
			node nou(i, j);
			int suma=v[i]+v[j];
			H[suma%PRIM].push_back(nou);
		}

	for (short i=1; i<nr_v; ++i)
		for (short j=i+1; j<=nr_v; ++j)
		{
			int suma=L-v[i]-v[j];
			if (suma > 0)
			{
				//sort(H[suma%PRIM].begin(), H[suma%PRIM].end(), cmp());
				check(suma, i, j);
			}
		}
	fstream g("oite.out", ios::out);
	g<<numar<<" ";
	g.close();
}

int main()
{
	read();
	solve();
	return 0;
}