Cod sursa(job #2745527)

Utilizator alexbrinzaAlexandru Brinza alexbrinza Data 26 aprilie 2021 17:35:16
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
using namespace std;

ifstream in("pariuri.in");
ofstream out("pariuri.out");

class Hash{
    static const int prime = 666013;
    vector < vector < tuple < int, int, int > > > hash;
    int S;

public:

    Hash(){
        hash.reserve(prime);
    }

    void set(int x)
    {
        S = x;
    }

    void insert(tuple < int, int, int > t)
    {
       int pos = (get<0>(t) + get<1>(t) + get<2>(t)) % prime;

       hash[pos].push_back(t);
    }

    bool search(tuple < int, int, int > t)
    {
        int sum = S - (get<0>(t) + get<1>(t) + get<2>(t));
        int pos = sum % prime;
        int ok = 0;

        for(int i = 0; i < hash[pos].size(); ++i)
            if(get<0>(hash[pos][i]) + get<1>(hash[pos][i]) + get<2>(hash[pos][i]) == sum)
            {
                out << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " ";
                out << get<0>(hash[pos][i]) << " " << get<1>(hash[pos][i]) << " " << get<2>(hash[pos][i]);
                ok = 1;
                break;
            }

        return ok;
    }

};

Hash h;
int n, s, x, nr;
vector < int > v;
vector < tuple < int, int, int > > sums;
bool solved;

int main()
{
    in >> n >> s;
    h.set(s);
    for(int i = 0; i < n; ++i)
    {
        in >> x;
        v.push_back(x);
    }
    for(int i = 0 ; i < v.size(); ++i)
        for(int j = i; j < v.size(); ++j)
            for(int k = j; k < v.size(); ++k)
                if(v[i] + v[j] + v[k] <= s)
                {
                    h.insert(make_tuple(v[i], v[j], v[k]));
                    sums.push_back(make_tuple(v[i], v[j], v[k]));
                }

    for(int i = 0; i < sums.size(); ++i)
    {
        bool val = h.search(sums[i]);

        if(val == 1)
        {
            solved = 1;
            break;
        }
    }

    if(solved == 0) out << -1;
    
    return 0;
}