Cod sursa(job #589860)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 14 mai 2011 10:17:37
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MOD 66013
#define MAX_N 1030

struct oaie
{
    unsigned int i:11;
    unsigned int j:11;
}__attribute__((packed));


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

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

    oaie w;
    w.i = i, w.j = j;
    H[k].push_back(w);
}

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

    for(vector<oaie>::iterator p = H[k].begin(); p != H[k].end(); ++p)
        if(V[p->i] + V[p->j] == x)
            if(p -> i > j && p -> j != j)
                ++Sol;
    return Sol;
}

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

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

void solve()
{
    sort(V+1, V+N+1);
    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("%d\n",Rez);
}

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

    citire();
    solve();
}