Cod sursa(job #75920)

Utilizator DastasIonescu Vlad Dastas Data 6 august 2007 17:44:59
Problema Oite Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

#define maxn 1024
#define maxp 666013

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

struct hash
{
    int i, j;
    hash *next;
};

int n;
int L;
int a[maxn];
hash *h[maxp] = {NULL};

void hadd(int p, int q)
{
    int t = (a[p] + a[q]) % maxp;
    hash *b = new hash;
    b->next = h[t];
    b->i = p;
    b->j = q;
    h[t] = b;
}

int hget(int p, int q)
{
    int s = 0;

    if ( L - (a[p] + a[q]) < 0 )
        return 0;



    hash *t = h[(L - (a[p] + a[q])) % maxp];

    while ( t )
    {
        if ( t->i > q )
            ++s;
        t = t->next;
    }

    if ( (L - (a[p] + a[q])) % maxp == (a[p] + a[q]) % maxp )
        h[(a[p] + a[q]) % maxp] = NULL;

    return s;
}

int main()
{
    fscanf(in, "%d %d", &n, &L);

    for ( int i = 0; i < n; ++i )
        fscanf(in, "%d", &a[i]);

    for ( int i = 0; i < n; ++i )
        for ( int j = i+1; j < n; ++j )
            hadd(i, j);

    int cnt = 0;
    for ( int i = 0; i < n; ++i )
        for ( int j = i+1; j < n; ++j )
            cnt += hget(i, j);

    fprintf(out, "%d\n", cnt);

	return 0;
}