Cod sursa(job #1689495)

Utilizator Mihai9Oniga Mihai Mihai9 Data 14 aprilie 2016 12:13:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <algorithm>
#define MOD 43143
#define w(x) (x&((1u<<21)-1))
#define set(x) mask[w(x)/32] |= (1u<<(31&x));
#define isok(x) (mask[w(x)/32] & (1u<<(31&x)))

using namespace std;

struct {
    unsigned nr, next;
} h[MOD + (1<<18)];

unsigned a[100], n, s, N, aloc = MOD;
unsigned mask[1<<18];

void baga(unsigned x){
    unsigned key = x%MOD;
    while (h[key].next)
        key = h[key].next;
    h[key].nr = x;
    h[key].next = aloc++;
}

int exista(unsigned x){
    unsigned key = x%MOD;
    while (h[key].next){
        if (h[key].nr == x) return 1;
        key = h[key].next;
    }
    return 0;
}

int main(){
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    scanf("%d %d", &n, &s);
    for (unsigned i=0; i<n; i++)
        scanf("%d ", a+i);
    for (unsigned i=0; i<n; i++)
        for (unsigned j=i; j<n; j++)
            for (unsigned k=j; k<n; k++)
                set((s-a[i]-a[j]-a[k]));
    for (unsigned i=0; i<n; i++)
        for (unsigned j=i; j<n; j++)
            for (unsigned k=j; k<n; k++)
                if (isok((a[i]+a[j]+a[k]))) baga(a[i]+a[j]+a[k]);
    for (unsigned i=0; i<n; i++)
        for (unsigned j=i; j<n; j++)
            for (unsigned k=j; k<n; k++){
                unsigned poz = 0;
                if (!exista(s-a[i]-a[j]-a[k])) continue;
                for (unsigned p1=0; p1<n; p1++)
                    for (unsigned p2=p1; p2<n; p2++)
                        for (unsigned p3=p2; p3<n; p3++)
                            if (a[p1]+a[p2]+a[p3] == s-a[i]-a[j]-a[k]){
                                printf("%d %d %d %d %d %d", a[i], a[j], a[k], a[p1], a[p2], a[p3]);
                                return 0;
                            }
            }
    printf("-1");
}