Cod sursa(job #476216)

Utilizator darrenRares Buhai darren Data 10 august 2010 12:11:44
Problema Oite Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<cstdio>
#include<fstream>
#include<list>
using namespace std;

const int MOD = 660013;
list<pair<int, int> > hash[MOD];

void add(int value)
{
	int nMOD = value % MOD;
	for (list<pair<int ,int> >::iterator it = hash[nMOD].begin(); it != hash[nMOD].end(); ++it)
		if ((*it).first == value)
		{
			++(*it).second;
			return;
		}
	hash[nMOD].push_back(make_pair(value, 1));
}

void del(int value)
{
	int nMOD = value % MOD;

	list<pair<int, int> >::iterator erase_pos;
	for (list<pair<int ,int> >::iterator it = hash[nMOD].begin(); it != hash[nMOD].end(); ++it)
		if ((*it).first == value && (*it).second == 1)
		{
			erase_pos = it;
			break;
		}
		else if ((*it).first == value)
		{
			--(*it).second;
			return;
		}
	hash[nMOD].erase(erase_pos);
}

int find(int value)
{
	int nMOD = value % MOD;
	for (list<pair<int ,int> >::iterator it = hash[nMOD].begin(); it != hash[nMOD].end(); ++it)
		if ((*it).first == nMOD)
			return (*it).second;
	return 0;
}

int n, r, a[1024], nsol;
int main()
{
	ifstream fin("oite.in");
	ofstream fout("oite.out");
	fin >> n >> r;
	for (int i = 0; i < n; ++i)
		fin >> a[i];

	for (int i = 2; i < n - 1; ++i)
		for (int j = i + 1; j < n; ++j)
			add(a[i] + a[j]);

	for (int i = 1; i < n; ++i)
	{
		for (int j = 0; j < i; ++j)
			nsol += find(r - a[i] - a[j]);
		for (int j = i + 2; j < n; ++j)
			del(a[i + 1] + a[j]);
	}

	fout << nsol;
}