Cod sursa(job #3129034)

Utilizator RealDream21Fabian-Andrei RealDream21 Data 12 mai 2023 12:12:59
Problema Loto Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <algorithm>

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 = 1000039, n, s, x, v[105];
    unordered_map<int, vector<int>> sume;
    //vector<vector<int>> cautare_rapida(p); // still tle => cautare binara :(
    fin >> n >> s;
    for(int i = 0; i < n; i++){
        fin >> v[i];
        //cautare_rapida[f_hash(v[i], p)].push_back(v[i]);
    }

    sort(v, v + n);

    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];
                int st = 0;
                int dr = n - 1;
                while(st <= dr)
                {
                    int mij = (st + dr)/2;
                    if(v[mij] == last){
                        found = true;
                        break;
                    }
                    if (last < v[mij])
                        dr = mij - 1;
                    else st = mij + 1;
                }
                if(found == true){
                    for(auto el: suma_partiala.second)
                        fout << el << " ";
                    fout << v[i] <<  " " << v[j] << " " << last;
                }
            }
        }
    }
    if(found == false)
        fout << -1;

    return 0;
}