Cod sursa(job #240165)

Utilizator Mishu91Andrei Misarca Mishu91 Data 6 ianuarie 2009 22:31:23
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MOD 66013
#define MAX_N 1025

struct oaie
{
    int nr, ind;
    int I[MAX_N], J[MAX_N];
};

int N, L, V[MAX_N];
vector <oaie> H[MOD];
long Rez;

void hash(int i, int j)
{
    int x = V[i] + V[j];
    if(x > L) return;
    int k = x % MOD;

    for(vector<oaie>::iterator it = H[k].begin(); it != H[k].end(); ++it)
        if(it -> nr == x)
        {
            ++it -> ind;
            it -> I[it -> ind] = i;
            it -> J[it -> ind] = j;
            return;
        }
    oaie w;
    w.nr = x, w.ind = 1;
    w.I[1] = i, w.J[1] = j;
    H[k].push_back(w);
}

int search(int i, int j)
{
    int x = L - V[i] - V[j];
    int k = x % MOD;
    int Sol = 0;

    for(vector<oaie>::iterator it = H[k].begin(); it != H[k].end(); ++it)
        if(it -> nr == x)
            for(int k = 1; k <= it -> ind; ++k)
                if(it -> I[k] > j && it -> J[k] != j)
                    ++Sol;
    return Sol;
}

void citire()
{
    scanf("%d %d",&N, &L);

    for(int i = 1; i <= N; ++i)
        scanf("%d",V+i);
}

void solve()
{
    for(int i = 1; i < N; ++i)
        for(int j = i+1; j <= N; ++j)
            hash(i, j);

    for(int i = 1; i < N; ++i)
        for(int j = i+1; j <= N; ++j)
            Rez += search(i, j);
    printf("%ld\n",Rez);
}

int main()
{
    freopen("oite.in","rt",stdin);
    freopen("oite.out","wt",stdout);

    citire();
    solve();
}