Cod sursa(job #1732727)

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

#define DIM 1000005

using namespace std;

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

struct bla {
    int val , p;
};

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].p = i * 10000 + j * 100 + 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].p / 10000] << " ";
                    v[pos].p %= 10000;

                    g << a[v[pos].p / 100];
                    v[pos].p %= 100;

                    g << " " << a[v[pos].p];
                    return 0;
                }
            }
        }
    }

    g << -1;
    return 0;
}