Cod sursa(job #613265)

Utilizator alex45meOlaru Alex alex45me Data 20 septembrie 2011 11:38:16
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#define N 1000001
typedef struct sum
{long x,y,z,t;};
long n,i,j,k,m,s,v[101],v1[101],nr,ok,a,b,p,l,q,u,x1[7],y1[7];
sum r[N],w[N];

void mer(long v[101],long p,long q)
{int m=(p+q)/2,i,j,k;
if(p==q)
      return;
mer(v,p,m);
mer(v,m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&v[i]<v[j]))
      v1[k++]=v[i++];
else
      v1[k++]=v[j++];
for(i=p;i<=q;i++)
      v[i]=v1[i];}

void merg(long x1[7],long p,long q)
{int m=(p+q)/2,i,j,k;
if(p==q)
      return;
merg(x1,p,m);
merg(x1,m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&x1[i]<x1[j]))
      y1[k++]=x1[i++];
else
      y1[k++]=x1[j++];
for(i=p;i<=q;i++)
      x1[i]=y1[i];}
      
void merge(sum r[N],long p,long q)
{int m=(p+q)/2,i,j,k;
if(p==q)
      return;
merge(r,p,m);
merge(r,m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&r[i].t<r[j].t))
      w[k++]=r[i++];
else
      w[k++]=r[j++];
for(i=p;i<=q;i++)
      r[i]=w[i];}

int main()
{freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%ld%ld",&n,&s);
for(i=1;i<=n;i++)
     scanf("%ld",&v[i]);
p=s;
mer(v,1,n);
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
for(k=j;k<=n;k++)
     nr++,r[nr].t=v[i]+v[j]+v[k],r[nr].x=v[i],r[nr].y=v[j],r[nr].z=v[k];
merge(r,1,nr);
for(q=1;q<nr;q<<=1);
for(i=1;i<=nr&&!ok;i++)
     {u=p-r[i].t;
     if(u<=0)
           break;
     for(j=0,m=q;m&&!ok;m>>=1)
     if(m+j<=nr)
           if(r[j+m].t<u)
                  j+=m;
           else
                  if(r[j+m].t==u)
                         ok=1,l=i,k=j+m;}
if(!ok)
     printf("-1");
else
     {x1[1]=r[l].x,x1[2]=r[l].y,x1[3]=r[l].z;
     x1[4]=r[k].x,x1[5]=r[k].y,x1[6]=r[k].z;
     merg(x1,1,6);
     printf("%ld %ld %ld %ld %ld %ld",x1[1],x1[2],x1[3],x1[4],x1[5],x1[6]);}
return 0;}