Cod sursa(job #2743963)

Utilizator mentolnothingmoreNegrut Maria Daniela mentolnothingmore Data 23 aprilie 2021 18:52:09
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <bits/stdc++.h>
#include <cstring>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

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

struct trio
{
    int x, y, z;
    friend ostream& operator <<(ostream&, const trio&);
    trio()
    {
        x = y = z = -1;
    }
    trio(int x, int y, int z)
    {
        this->x = x;
        this->y = y;
        this->z = z;
    }
};

ostream& operator <<(ostream& out, const trio& t)
{
    out << t.x << " " << t.y << " " << t.z << " ";
    return out;
}


unordered_map<long long, trio> solution_sum;
vector <long long> nr, sums;
int N;
long long S, x, s_nr;

bool binarySearch(int left, int right, int val)
{
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (sums[mid] == val) return true;
        if (sums[mid] > val)
            right = mid;
        else if (sums[mid] < val) left = mid + 1;
    }
    return false;
}

void sumGen(int poz)
{
    if (poz >= N)
        return;
    for (int i = poz; i < N; ++i)
        for (int j = i; j < N; ++j)
        {
            if (!binarySearch(0, sums.size(), nr[poz] + nr[i] + nr[j]))
            {
                solution_sum[nr[poz] + nr[i] + nr[j]].x = nr[poz];
                solution_sum[nr[poz] + nr[i] + nr[j]].y = nr[i];
                solution_sum[nr[poz] + nr[i] + nr[j]].z = nr[j];
                sums.push_back(nr[poz] + nr[i] + nr[j]);
            }
        }
    sumGen(poz + 1);
}

int main()
{
    fin >> N >> S;
    for (int i = 0; i < N; ++i)
    {
        fin >> x;
        nr.push_back(x);
    }
    sumGen(0);
    sort(sums.begin(), sums.end());
    s_nr = sums.size();
    int solution = -1, index_sum = 0;
    while (solution == -1 && index_sum <= s_nr)
    {
        if (binarySearch(0, s_nr, S - sums[index_sum]))
        {
            fout << solution_sum[sums[index_sum]];
            fout << solution_sum[ S - sums[index_sum]];
            solution = 0;
        }
        index_sum++;
    }
    if (solution == -1)
        fout << -1;
    return 0;
}