Cod sursa(job #2954619)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 14 decembrie 2022 22:05:36
Problema Oite Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 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,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);
    /*for(i=1;i<=lg;i++)
    {
        if(first[sum[i].val]==0)
            first[sum[i].val]=i;
        last[sum[i].val]=i;
    }*/
    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++)
        {
            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;
}