Cod sursa(job #1732735)

Utilizator cristina_borzaCristina Borza cristina_borza Data 22 iulie 2016 14:41:04
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <algorithm>
#include <fstream>
#include <cstdio>

#define DIM 1000005

using namespace std;

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;
}

void read(int &x) {
    char ch;
    x = 0;

    while (!isdigit(ch = getchar())) {

    }

    do {
        x = x * 10 + ch - '0';
    }while (isdigit(ch = getchar()));
}

int main() {
    freopen("loto.in" , "r" , stdin);
    freopen("loto.out" , "w" , stdout);

    read(n) , read(s);
    for (int i = 1; i <= n; ++i) {
        read(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) {
                    printf("%d %d %d %d " , a[i] , a[j] , a[k] , a[v[pos].p / 10000]);
                    v[pos].p %= 10000;

                    printf("%d " , a[v[pos].p / 100]);
                    v[pos].p %= 100;

                    printf("%d" , a[v[pos].p]);
                    return 0;
                }
            }
        }
    }

    printf("-1");
    return 0;
}