Cod sursa(job #2954638)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 14 decembrie 2022 22:19:40
Problema Oite Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oite.in");
ofstream fout("oite.out");
map<long long,bool>h;
struct sume
{
    int val,x,y;
}sum[1030*1030];
int n,s,v[1030],i,j,lg,start,finish,cnt,ok,k,l,val;
long long p[5],ans,x;
int schema[6];
bool cmp(sume a,sume b)
{
    return a.val<b.val;
}
long long getHash(int a[])
{
    ans=0;
    for(l=1;l<=4;++l)
        ans=ans+p[l-1]*a[l];
    return ans;
}
signed main()
{
    p[0]=1;
    for(i=1;i<=3;++i)
        p[i]=p[i-1]*1025;
    fin>>n>>s;
    for(i=1;i<=n;++i)
        fin>>v[i];
    ///sort(v+1,v+n+1);
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
            if(v[i]!=v[j])
            {
                ++lg;
                sum[lg].val=v[i]+v[j];
                sum[lg].x=i;
                sum[lg].y=j;
            }
    sort(sum+1,sum+lg+1,cmp);
    start=finish=lg;
    for(i=1;i<=lg;++i)
    {
        if(sum[i].val>s/2)
            break;
        val=s-sum[i].val;
        while(sum[finish].val>val)
            --finish;
        while(sum[start].val>=val)
            --start;
        ++start;
        if(start==lg+1)
            --start;
        if(sum[finish].val!=val)
            continue;
        for(j=start;j<=finish;++j)
        {
            if(sum[i].x==sum[j].x || sum[i].x==sum[j].y || sum[i].y==sum[j].x || sum[i].y==sum[j].y)
                continue;
            schema[1]=sum[i].x;
            schema[2]=sum[i].y;
            schema[3]=sum[j].x;
            schema[4]=sum[j].y;
            sort(schema+1,schema+5);
            ok=1;
            if(ok==1)
            {
                x=getHash(schema);
                if(h[x]==0)
                {
                    ++cnt;
                    h[x]=1;
                }
            }
        }
    }
    fout<<cnt<<'\n';
    return 0;
}