Cod sursa(job #2954612)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 14 decembrie 2022 21:55:15
Problema Oite Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oite.in");
ofstream fout("oite.out");
unordered_map<int,int>first,last;
unordered_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;
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);
    for(i=1;i<=lg;i++)
    {
        if(first[sum[i].val]==0)
            first[sum[i].val]=i;
        last[sum[i].val]=i;
    }
    for(i=1;i<=lg;i++)
    {
        if(sum[i].val>s/2)
            break;
        if(!first[s-sum[i].val])
            continue;
        start=first[s-sum[i].val];
        finish=last[s-sum[i].val];
        for(j=start;j<=finish;j++)
        {
            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;
            for(k=2;k<=4;k++)
                if(schema[k]==schema[k-1])
                    ok=0;
            if(ok==1)
            {
                x=getHash(schema);
                if(h[x]==0)
                {
                    cnt++;
                    h[x]=1;
                }
            }
        }
    }
    fout<<cnt<<'\n';
    return 0;
}