Cod sursa(job #76051)

Utilizator DastasIonescu Vlad Dastas Data 7 august 2007 18:31:03
Problema Oite Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <vector>

using namespace std;

#define maxn 1024
#define maxp 204729
#define maxp2 154729

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

struct hash
{
    short i, j;
};

int n;
int L;
int a[maxn];
vector<hash> h[maxp];
int nr[maxp];
vector<hash> h2[maxp2];
int nr2[maxp2];

void hadd(int p, int q)
{
    int t = (a[p] + a[q]) % maxp;
    int d = (a[p] + a[q]) % maxp2;

    hash tt;
    tt.i = p;
    tt.j = q;

    if ( nr[t] < nr2[d] )
        h[t].push_back(tt), ++nr[t];
    else
        h2[d].push_back(tt), ++nr2[d];
}

int hget(int p, int q)
{
    if ( L - (a[p] + a[q]) < 0 )
        return 0;

    int s = 0;
    int v = (L - (a[p] + a[q]));
    int t = v % maxp;
    int d = v % maxp2;

    int i = 0;
    if ( nr[t] < nr2[d] )
    {
        for ( i = 0; i != nr[t]; ++i )
        {
            if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
                ++s;
            if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
                ++s;
        }
        for ( ; i != nr2[d]; ++i )
            if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
                ++s;
    }
    else
    {
        for ( i = 0; i != nr2[d]; ++i )
        {
            if ( h2[d][i].i > q && a[h2[d][i].i] + a[h2[d][i].j] == v )
                ++s;
            if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
                ++s;
        }
        for ( ; i != nr[t]; ++i )
            if ( h[t][i].i > q && a[h[t][i].i] + a[h[t][i].j] == v )
                ++s;
    }

    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;
}