Cod sursa(job #2504730)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 5 decembrie 2019 14:09:47
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 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,Bin[2000005],c=0;

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

int Binary(int x)
{
    int sol=-1,left=1,right=c;
    while(left<=right)
    {
        int mij=(left+right)/2;
        if(Bin[mij]==x)
        {
            sol=mij;
            break;
        }
        if(Bin[mij]>x)
            right=mij-1;
        if(Bin[mij]<x)
            left=mij+1;
    }
    return sol;
}

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)
                {
                    c++;
                    Bin[c]=aux;
                }
            }
        }
    }
    sort(Bin+1,Bin+1+c);
    for(int i=1;i<=c;i++)
    {
        if(Bin[i]<=S)
        {
            int aux=S-Bin[i];
            if(Binary(aux)>=0)
            {
                Sol(aux,Bin[i]);
                ok=1;
                break;
            }
        }
        else
            break;
    }
    if(!ok)
        fout<<-1<<'\n';
}