Cod sursa(job #290805)

Utilizator lsorin_94Lodoaba Sorin lsorin_94 Data 28 martie 2009 19:18:47
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
struct sumulus{long i1,i2,i3,s;}x[200000];
long n,i,j,k,a[1005],l,ss,s,st,dr,m;
int partit(sumulus a[ ],int st, int dr)
{int i,j,m,piv;
 sumulus aa;
 m=(st+dr)/2;
 piv=a[m].s;
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].s<piv);
   do{--j;} while(a[j].s>piv);
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(sumulus a[ ],int st,int dr)
{int p;
 if (st<dr)
   {p=partit(a,st,dr);
	quicks(a,st,p);
	quicks(a,p+1,dr);
   }
}

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",&a[i]);
 for(i=1;i<=n;++i)
    for(j=i;j<=n;++j)
       for(k=j;k<=n;++k)
          {x[++l].i1=a[i];
           x[l].i2=a[j];
           x[l].i3=a[k];
           x[l].s=x[l].i1+x[l].i2+x[l].i3;}
 quicks(x,1,l);
 if(x[l].s*2<s){printf("-1\n");return 0;}
 for(i=1;i<=l;++i)
    {st=i;dr=l;
     ss=s-x[i].s;
     while(st<=dr)
      {m=st+dr;m/=2;
       if(x[m].s==ss){printf("%ld %ld %ld %ld %ld %ld\n",x[i].i1,x[i].i2,x[i].i3,x[m].i1,x[m].i2,x[m].i3);return 0;}
       if(x[m].s<ss)st=m+1;
               else dr=m-1;}}
 printf("-1\n");
 return 0;
}