Cod sursa(job #2513814)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 23 decembrie 2019 20:15:56
Problema Oite Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("oite.in");
ofstream fout("oite.out");

#define ll long long
#define MOD 66013
#define x first
#define y second
#define mp make_pair

vector < pair< pair<int,int>, pair<int,int> > > Hash[MOD];

ll L,S=0;

int n,v[2024],ok=0,nr=0;

void Read()
{
    fin>>n>>L;
    for(int i=1;i<=n;i++)
        fin>>v[i];
}

void Push_Hash(int i, int j, int k, int m)
{
    int s[5],cnt=4;
    ok=0;
    s[1]=i;s[2]=j;s[3]=k;s[4]=m;
    sort(s+1,s+1+cnt);
    int l=(i+j+k+m)%MOD;
    for(unsigned ct=0;ct<Hash[l].size();ct++)
    {
        int a=Hash[l][ct].x.x;
        int b=Hash[l][ct].x.y;
        int c=Hash[l][ct].y.x;
        int d=Hash[l][ct].y.y;
        if(a==s[1] && b==s[2] && c==s[3] && d==s[4])
        {
            ok=1;
            break;
        }
    }
    if(!ok)
        Hash[l].push_back(mp(mp(s[1],s[2]),mp(s[3],s[4])));
}

bool OK(int i, int j, int k, int m)
{
    int s[5];
    s[1]=i;s[2]=j;s[3]=k;s[4]=m;
    for(int i=1;i<4;i++)
    {
        for(int j=i+1;j<=4;j++)
        {
            if(s[i]==s[j])
                return 0;
        }
    }
    return 1;
}

void Sol()
{
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                for(int m=k+1;m<=n;m++)
                {
                    S=v[i]+v[j]+v[k]+v[m];
                    if(S==L)
                    {
                        ok=0;
                        Push_Hash(i,j,k,m);
                        if(!ok && OK(i,j,k,m))
                            nr++;
                    }
                }
            }
        }
    }
}

int main()
{
    Read();
    Sol();
    fout<<nr<<'\n';
}