Cod sursa(job #2496299)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 20 noiembrie 2019 17:27:52
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct pii
{

    int first, a1,a2,a3;

};

const int MOD = 12289;

vector<pii> Hash[MOD];

int n,s;
int a[105];

void Read()
{
    int i;
    fin>>n>>s;
    for(i=1; i<=n; ++i)
        fin>>a[i];
    sort(a+1,a+n+1);
}

void Add(int val, int i, int j, int k)
{
    int key = val%MOD;
    pii aux;
    aux.first = val;
    aux.a1 = i;
    aux.a2 = j;
    aux.a3 = k;
    Hash[key].push_back(aux);
}

int CB(int key, int val,int s, int d)
{
    if(s>=d)
        return -1;
    int mid = s+(d-s)/2;
    if(Hash[key][mid].first == val)
        return mid;
    if(Hash[key][mid].first < val)
        return CB(key, val, s, mid);
    else return CB(key, val, mid+1,d);
}

int Search(int val)
{
    int key = val%MOD;
    int poz = CB(key, val,0,Hash[key].size());
    if(poz!=-1)
        return poz;
    return -1;
}

void Do()
{
    int i,j,k;
    int sum;
    int poz;
    int key;
    bool found = false;
    Read();
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            for(k=1; k<=n; ++k)
            {
                sum = a[i]+a[j]+a[k];
                Add(sum,i,j,k);
            }
    for(i=1; i<=n && found ==false; ++i)
        for(j=1; j<=n && found == false; ++j)
            for(k=1; k<=n; ++k)
            {
                sum = a[i] + a[j] + a[k];
                if(s-sum>=0)
                {
                    poz = Search(s-sum);
                    if(poz>-1)
                    {
                        key = (s-sum)%MOD;
                        fout<<a[Hash[key][poz].a1]<<" "<<a[Hash[key][poz].a2]<<" "<<a[Hash[key][poz].a3]<<" "<<a[i]<<" "<<a[j]<<" "<<a[k];
                        found = true;
                        break;
                    }
                }
            }
    if(found == false)
        fout<<-1;
}

int main()
{
    Do();
    return 0;
}