Cod sursa(job #332267)

Utilizator freak93Adrian Budau freak93 Data 17 iulie 2009 11:13:18
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("oite.in");
ofstream g("oite.out");

const int maxn=1024;
const int prime=224737;
const int mod=1<<18-1;

int n,l,a[maxn],i,j,k;

struct nod
{
    int o1;
    int o2;
    int l;
} lana[maxn*maxn];

struct hi
{
    nod a;
    hi *next;
}
*hash[mod+1];

void insert(nod a)
{
    long long list=a.l*prime;
    list&=mod;
    hi *k=new hi;
    k->next=hash[list];
    k->a=a;
    hash[list]=k;
}

int main()
{
    f>>n>>l;
    for(i=1;i<=n;++i)
        f>>a[i];
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
            lana[++k].o1=i,lana[k].o2=j,lana[k].l=a[i]+a[j];
    insert(lana[1]);
    hi *it;
    long long list;
    int x,fel=0;
    for(i=2;i<=k;++i)
    {
        x=l-lana[i].l;
        list=x*prime;
        list&=mod;
        for(it=hash[list];it;it=it->next)
            if(it->a.l==x)
                if(it->a.o2<lana[i].o1)
                    ++fel;
        insert(lana[i]);
    }

    g<<fel<<"\n";

    f.close();
    g.close();

    return 0;
}