Cod sursa(job #1120372)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 24 februarie 2014 23:30:43
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
#include<vector>

using namespace std;

typedef pair<int,int> PII;
typedef pair<int,PII> Elm;
const int MOD = 666013;
const int NMAX = 1024+4;

bool Diferit(PII x,PII y)
{
    if(x.first==y.first || x.first==y.second || x.second==y.first || x.second==y.second) return 0;
    return 1;
}

struct Hash
{
    vector<Elm> H[MOD+2];

    void Adauga(int x,int i,int j)
    {
        int r=x%MOD;
        H[r].push_back(make_pair(x,make_pair(i,j)));
    }

    bool Cauta(int x,int i,int j)
    {
        int r=x%MOD;
        vector<Elm>::iterator it;
        for(it=H[r].begin(); it!=H[r].end(); it++)
            if(it->first==x && Diferit(it->second,make_pair(i,j))) return 1;
        return 0;
    }
};

int N,L,Sol;
int A[NMAX];
Hash H;

int main()
{
    int i,j;

    freopen("oite.in","r",stdin);
    freopen("oite.out","w",stdout);

    scanf("%d%d",&N,&L);

    for(i=1; i<=N; i++)
        scanf("%d",&A[i]);

    for(i=1; i<=N; i++)
        for(j=i+1; j<=N; j++)
            H.Adauga(A[i]+A[j],i,j);

    for(i=1; i<=N; i++)
        for(j=i+1; j<=N; j++)
            Sol+=H.Cauta(L-(A[i]+A[j]),i,j);

    printf("%d\n",Sol/4);

    return 0;
}