Cod sursa(job #2214751)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 19 iunie 2018 23:49:53
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <vector>
#include <fstream>
#include <algorithm>

#define VMAX 110

using std::sort;
using std::vector;

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

struct Comb {
    int sum;
    int a, b, c;
};

inline bool operator<(Comb a, Comb b) {
    return a.sum < b.sum;
}

int n, s;
int v[VMAX];
vector<Comb> comb;

int binSrch(int sum) {
    int lo = -1, hi = comb.size();
    while (hi - lo > 1) {
        int md = (lo + hi) >> 1;
        if (sum > comb[md].sum)
            lo = md;
        else
            hi = md;
    }

    if (hi < comb.size() && comb[hi].sum == sum)
        return hi;
    return -1;
}

int main() {
    fin >> n >> s;
    for (int i = 0; i < n; i++)
        fin >> v[i];

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

    sort(comb.begin(), comb.end());
    for (int i = 0; i < comb.size(); i++) {
        int j = binSrch(s - comb[i].sum);
        if (j != -1) {
            fout << comb[i].a << ' ' << comb[i].b << ' ' << comb[i].c << ' '
                 << comb[j].a << ' ' << comb[j].b << ' ' << comb[j].c << '\n';

            fout.close();
            return 0;
        }
    }

    fout << "-1\n";
    fout.close();
    return 0;
}