Cod sursa(job #2014409)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 23 august 2017 16:23:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>
#include <algorithm>
#define H 666013
#define CMAX 1000000
#define NMAX 100
using namespace std;
int lista[H],urm[CMAX+1],sum[CMAX+1],a[CMAX+1],b[CMAX+1],c[CMAX+1],v[NMAX+1],rez[6];
int main()
{
    int n,s,i,j,k,nr,z,t,ct;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    for(i=1; i<=n; i++)
        scanf("%d",&v[i]);
    sort(v+1,v+1+n);
    nr=0;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
            {
                z=v[i]+v[j]+v[k];
                t=lista[z%H];
                while(sum[t]!=0 && sum[t]<z)
                    t=urm[t];
                if(sum[t]==0 || sum[t]!=z)
                {
                    nr++;
                    if(t!=0)
                    {
                        urm[nr]=urm[t];
                        urm[t]=nr;
                    }
                    else
                        lista[z%H]=nr;
                    sum[nr]=z;
                    a[nr]=v[i];
                    b[nr]=v[j];
                    c[nr]=v[k];
                }
            }
    ct=1;
    for(i=1; i<=n && ct; i++)
        for(j=1; j<=n && ct; j++)
            for(k=1; k<=n && ct; k++)
            {
                z=v[i]+v[j]+v[k];
                if(z<s){
                    t=lista[(s-z)%H];
                    while(sum[t]!=0 && sum[t]<s-z)
                        t=urm[t];
                    if(sum[t]==s-z)
                    {
                        rez[0]=a[t];
                        rez[1]=b[t];
                        rez[2]=c[t];
                        rez[3]=v[i];
                        rez[4]=v[j];
                        rez[5]=v[k];
                        ct=0;
                    }
                }
            }
    if(ct==1)
        printf("-1\n");
    else
    {
        sort(rez,rez+6);
        for(i=0; i<6; i++)
            printf("%d ",rez[i]);
    }
    return 0;
}