Cod sursa(job #2504729)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 5 decembrie 2019 14:03:41
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
 
using namespace std;
 
ifstream fin("loto.in");
ofstream fout("loto.out");
 
#define MOD 660013
#define mp make_pair
#define x first
#define y second
 
int v[105],n,S,ans;
 
vector <int> Bin;
vector < pair< pair<int,int>, pair<int,int> > > Hash[MOD];
 
void FindHash(int val, int a, int b, int c)
{
    int l=val%MOD,ok=0;
    for(unsigned j=0;j<Hash[l].size();j++)
    {
        if(Hash[l][j].x.x==val)
        {
            ok=1;
            ans=1;
            break;
        }
    }
    if(!ok)
        Hash[l].push_back(mp(mp(val,a),mp(b,c)));
}
 
void Sol(int S1, int S2)
{
    int l1=S1%MOD,l2=S2%MOD;
    for(unsigned j=0;j<Hash[l1].size();j++)
    {
        if(Hash[l1][j].x.x==S1)
        {
            fout<<Hash[l1][j].x.y<<" "<<Hash[l1][j].y.x<<" "<<Hash[l1][j].y.y<<" ";
            break;
        }
    }
    for(unsigned j=0;j<Hash[l2].size();j++)
    {
        if(Hash[l2][j].x.x==S2)
        {
            fout<<Hash[l2][j].x.y<<" "<<Hash[l2][j].y.x<<" "<<Hash[l2][j].y.y<<" ";
            break;
        }
    }
}
 
bool ok=0;
 
int main()
{
    fin>>n>>S;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int aux=v[i]+v[j]+v[k];
                ans=0;
                FindHash(aux,v[i],v[j],v[k]);
                if(!ans)
                    Bin.push_back(aux);
            }
        }
    }
    sort(Bin.begin(),Bin.end());
    vector <int> ::iterator it;
    for(it=Bin.begin();it!=Bin.end();it++)
    {
        if(*it<=S)
        {
            int aux=S-*it;
            if(binary_search(Bin.begin(),Bin.end(),aux))
            {
                Sol(*it,aux);
                ok=1;
                break;
            }
        }
    }
    if(!ok)
        fout<<-1<<'\n';
}