Cod sursa(job #1755251)

Utilizator crushackPopescu Silviu crushack Data 9 septembrie 2016 17:21:46
Problema Loto Scor 70
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.66 kb
#include <stdio.h>
#include <algorithm>
#define NMax (1<<7)
#define LMax NMax*NMax*NMax
using namespace std;

const char IN[]="loto.in",OUT[]="loto.out";

struct entry{
    int x,a1,a2,a3;
    bool operator<(entry const &b) const{
        return x<b.x;
    }
    bool operator<=(entry const &b) const{
        return x<=b.x;
    }
    bool operator==(entry const &b) const{
        return x==b.x;
    }
    bool operator!=(entry const &b) const{
        return x!=b.x;
    }
} c[LMax];

int N,S,L;
int R[6];
int a[NMax];

int search(int _x)
{
    int i,step;
    static entry x;x.x=_x;
    for ( step = 1 ; step < L ; step<<=1 );
    for (i=-1;step;step>>=1)
        if (i+step<L && c[i+step]<=x)
            i+=step;
    if (i==-1 || c[i]!=x) return -1;
    return i;
}

void solve()
{
    int i,j,k,r;

    for (i=0;i<N;++i)
        for (j=0;j<N;++j)
            for (k=0;k<N;++k)
                c[L].x= a[i] + a[j] + a[k] , c[L].a1=i , c[L].a2=j , c[L].a3=k , ++L;

    sort(c,c+L);
    L=unique(c,c+L)-c;
    for (i=0;i<N;++i)
        for (j=0;j<N;++j)
            for (k=0;k<N;++k)
            {
                r=search( S- (a[i] + a[j] + a[k]) );
                if (r!=-1)
                {
                    R[0]=a[i];R[1]=a[j];R[2]=a[k];R[3]=a[c[r].a1];R[4]=a[c[r].a2];R[5]=a[c[r].a3];
                    return;
                }
            }
    R[0]=-1;
    return;
}

int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%d%d",&N,&S);
    for (i=0;i<N;++i) scanf("%d",a+i);
    fclose(stdin);

    solve();

    freopen(OUT,"w",stdout);
    if (R[0]==-1) printf("-1");
    else for (i=0;i<6;++i) printf("%d ",R[i]);
    printf("\n");
    fclose(stdout);

    return 0;
}