Cod sursa(job #2565135)

Utilizator antoniu200Alexa Sergiu antoniu200 Data 2 martie 2020 12:23:09
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("loto.in");
ofstream cout("loto.out");

struct elements_of_sum {
    unsigned e1, e2, e3;
    unsigned val;
};

elements_of_sum make_elements(unsigned e1, unsigned e2, unsigned e3, unsigned val) {
    elements_of_sum x;
    x.e1 = e1, x.e2 = e2, x.e3 = e3, x.val = val;
    return x;
}

bool operator<(elements_of_sum x, elements_of_sum y) {
    return x.val < y.val;
}

ostream& operator<<(ostream& strm, elements_of_sum x) {
    strm << x.e1 << " " << x.e2 << " " << x.e3;
    return strm;
}

int main() {
    unsigned out_of, sum;
    cin >> out_of >> sum;
    unsigned nums[out_of];
    for (unsigned i = 0; i < out_of; i++)
        cin >> nums[i];

    vector<elements_of_sum> sums;
    for (unsigned i = 0; i < out_of; i++)
        for (unsigned j = i; j < out_of; j++)
            for (unsigned k = j; k < out_of; k++)
                sums.emplace_back(make_elements(nums[i], nums[j], nums[k], nums[i] + nums[j] + nums[k]));

    sort(sums.begin(), sums.end());
    for (unsigned i = 0; i < sums.size(); i++) {
        unsigned lhs = i, rhs = sums.size() - 1, mid;
        while (lhs < rhs) {
            mid = (lhs + rhs) / 2;
            if (sums[mid].val + sums[i].val < sum)
                lhs = mid + 1;
            else if (sums[mid].val + sums[i].val > sum)
                rhs = mid - 1;
            else {
                cout << sums[mid] << " " << sums[i];
                return 0;
            }
        }
    }
    cout << "-1";
}