Cod sursa(job #1732721)

Utilizator cristina_borzaCristina Borza cristina_borza Data 22 iulie 2016 14:31:03
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <algorithm>
#include <fstream>

#define DIM 1000005

using namespace std;

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

struct bla {
    int val , v1 , v2 , v3;
};

bla v[DIM];

int n , s , nr , a[DIM];

bool comp(bla a , bla b) {
    return a.val < b.val;
}

int caut_bin (int x) {
    int i , p = 0;
    for (i = 1; i <= nr; i <<= 1);
    while (i) {
        if (i + p <= nr && v[i + p].val <= x) {
            p += i;
        }
        i >>= 1;
    }

    return p;
}

int main() {
    f >> n >> s;
    for (int i = 1; i <= n; ++i) {
        f >> a[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            for (int k = j; k <= n; ++k) {
                ++nr;
                v[nr].val = a[i] + a[j] + a[k];

                v[nr].v1 = i;
                v[nr].v2 = j;
                v[nr].v3 = k;
            }
        }
    }

    sort (v + 1, v + nr + 1 , comp);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                int sum = a[i] + a[j] + a[k];
                int pos = caut_bin(s - sum);

                if (v[pos].val == s - sum) {
                    g << a[i] << " " << a[j] << " " << a[k] << " " << a[v[pos].v1] << " " << a[v[pos].v2] << " " << a[v[pos].v3];
                    return 0;
                }
            }
        }
    }

    g << -1;
    return 0;
}