Cod sursa(job #72207)

Utilizator peanutzAndrei Homorodean peanutz Data 13 iulie 2007 00:05:28
Problema Oite Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>
#define NMAX 10030
#define MOD 400033
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;

int a[NMAX];
vector<int> x[MOD], y[MOD];
long long nr;
int n, l;

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

inline void insert(int i, int j)
{
         int h = (a[i] + a[j]) % MOD;
		
	    x[h].pb(i);
        y[h].pb(j);
        //printf("am bagat in hash %d si %d la pozitia %d\n", i, j, h);
}	

void fillhash()
{
	int i, j;
	for(i = 1; i < n; ++i)
		for(j = i+1; j <= n; ++j)
			insert(i, j);
}

void solve()
{
	int i, j, k;
	int s, dif, initial, until, max;

	for(i = 1; i < n; ++i)
		for(j = i+1; j <= n; ++j)
		{	
            initial = l - a[i] - a[j];
			dif = initial % MOD;


            //printf("caut dif = %d pentru %d si %d\n", dif, i, j);
			for(k = 0, until = x[dif].size(); k < until; ++k)
			{
				if(a[ x[dif][k] ] + a[ y[dif][k] ] != initial || x[dif][k] == i || x[dif][k] == j || y[dif][k] == i || y[dif][k] == j)
				{

                    //printf("am gasit %d si %d\n", x[dif][k], y[dif][k]);
                }
                else
                    ++nr;
			}
            //printf("\n\n");
		}
}

int main()
{
	freopen("oite.in", "r", stdin);
	freopen("oite.out", "w", stdout);
	
	read();

	fillhash();

	solve();

	printf("%lld\n", nr/6);

	return 0;
}