Cod sursa(job #1974304)

Utilizator savigunFeleaga Dragos-George savigun Data 27 aprilie 2017 12:51:58
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

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

int n, s, v[101], ns;
Triple sums[1000001];
const int L = 1 << 20;
Triple t;

bool compare(Triple a, Triple b) {
    return a.sum < b.sum;
}

int bsearch(int val) {
    int pas = L;
    int p = 0;
    while (pas != 0) {
        if (p + pas <= ns && sums[p + pas].sum <= val) {
            p += pas;
        }
        pas /= 2;
    }

    return p;
}


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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                t.sum = v[i] + v[j] + v[k];
                t.a = v[i];
                t.b = v[j];
                t.c = v[k];
                sums[++ns] = t;
            }
        }
    }

    sort(sums + 1, sums + ns + 1, compare);

    bool found = false;

    for (int i = 1; i <= n && !found; ++i) {
        for (int j = 1; j <= n && !found; ++j) {
            for (int k = 1; k <= n && !found; ++k) {
                int sum = v[i] + v[j] + v[k];
                int dif = s - sum;
                if (dif < 0) break;
                int idx = bsearch(dif);
                if (sums[idx].sum == dif) {
                    out << v[i] << " " << v[j] << " " << v[k] << " ";
                    out << sums[idx].a << " " << sums[idx].b << " " << sums[idx].c;
                    found = true;
                }
            }
        }
    }

    if (!found) {
        out << -1;
    }

    return 0;
}