Cod sursa(job #3154660)

Utilizator catalinmarincatalinmarin catalinmarin Data 5 octombrie 2023 15:43:18
Problema Loto Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("loto.in");
ofstream cout("loto.out");
vector<tuple<int, int, int, int>> sume;
bool compare(tuple<int, int, int, int> a, tuple<int, int, int, int> b){
    return get<0>(a) < get<0>(b);
}
int binary_search(int left, int right, int nr){
    int rezultat = 0;
    while (left <= right){
        int mid = (left + right) / 2;
        if (nr <= get<0>(sume[mid])){
            right = mid - 1;
            rezultat = mid;
        } else {
            left = mid + 1;
        }
    }
    if (get<0>(sume[rezultat]) == nr)
        return rezultat;
    return -1;
}
int main(){
    int n, suma;
    int numere[101];
    cin >> n >> suma;
    for (int i = 1; i <= n; i++){
        cin >> numere[i];
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= n; k++) {
                sume.push_back(make_tuple(numere[i] + numere[j] + numere[k], numere[i], numere[j], numere[k]));
            }
        }
    }
    sort(sume.begin(), sume.end(), compare);
    for (int i = 0; i < sume.size(); i++){
        int complement_binar = suma - get<0>(sume[i]);
        int right = sume.size() - 1;
        int ind_gasit = binary_search(0, right, complement_binar);
        if (get<0>(sume[ind_gasit]) == complement_binar){
            cout << get<1>(sume[ind_gasit]) << " " << get<2>(sume[ind_gasit]) << " " << get<3>(sume[ind_gasit]) << " ";
            cout << get<1>(sume[i]) << " " << get<2>(sume[i]) << " " << get<3>(sume[i]);
            exit(0);
        }
    }
    cout << -1;
    return 0;
}