Cod sursa(job #3128998)

Utilizator RealDream21Fabian-Andrei RealDream21 Data 11 mai 2023 22:24:03
Problema Loto Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>

using namespace std;


int f_hash(int n, int p)
{
    return n % p;
}

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

    int p = 666013, n, s, x, v[105];
    unordered_map<int, vector<int>> sume;
    vector<vector<int>> cautare_rapida(666013);
    fin >> n >> s;
    for(int i = 0; i < n; i++){
        fin >> v[i];
        cautare_rapida[f_hash(v[i], p)].push_back(v[i]);
    }

    for(int i = 0; i < n; i++)
        for(int j = i ; j < n; j++)
            for(int k = j; k < n; k++)
                sume[v[i] + v[j] + v[k]] = {v[i], v[j], v[k]};

    bool found = false;
    for (auto suma_partiala: sume){
        int ramas = s - suma_partiala.first;
        for(int i = 0; i < n && !found; i++){
            for(int j = 0; j < n && !found; j++){
                int last = ramas - v[i] - v[j];
                if(last < 0)
                    break;
                int whereLast = f_hash(last, p);
                bool foundLast = false;
                for(int i = 0; i < cautare_rapida[whereLast].size(); i++)
                    if(cautare_rapida[whereLast][i] == last){
                        foundLast = true;
                        break;
                    }
                if(foundLast == true){
                    found = true;
                    fout << v[i] << " " << v[j] << " " << last << " ";
                    for(auto el: suma_partiala.second)
                        fout << el << " ";
                }
            }
        }
    }
    if(found == false)
        fout << -1;

    return 0;
}