Cod sursa(job #142221)

Utilizator razvi9Jurca Razvan razvi9 Data 24 februarie 2008 12:48:56
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
int a[101],n,i,j,k,S,nr,st,dr,mij,s1;
struct {int i,j,k;int s;} s[1000001],aux;

inline int poz(int st,int dr)
{int y=0,x=-1,au;
 while(st<dr)
 {if(s[st].s>s[dr].s)
   {aux=s[st];s[st]=s[dr];s[dr]=aux;
    au=y;y=-x;x=-au;}
  st=st+y;
  dr=dr+x;}
 return st;
}

void qsort(int stanga,int dreapta)
{if(stanga>=dreapta) return ;
 int k=poz(stanga,dreapta);
 qsort(stanga,k-1);
 qsort(k+1,dreapta);}


int main()
{freopen("loto.in","r",stdin);
 freopen("loto.out","w",stdout);
 scanf("%d %d",&n,&S);
 for(i=1;i<=n;i++)
 {scanf("%d",&a[i]);}
 for(i=1;i<=n;i++)
  for(j=i;j<=n;j++)
   for(k=j;k<=n;k++)
    s[++nr].s=a[i]+a[k]+a[j],s[nr].i=a[i],s[nr].j=a[j],s[nr].k=a[k];
 qsort(1,nr);
 for(i=1;i<=nr;i++){
	  st=i;dr=nr;
	  s1=S-s[i].s;
	  while(st<dr){
		  mij=(st+dr)>>1;
		  if(s[mij].s==s1) break;
		  if(s[mij].s>s1) dr=mij-1;
		  else st=mij+1;}
	  if(s[mij].s==s1){
		  j=mij;
		  printf("%d %d %d %d %d %d",s[i].i,s[i].j,s[i].k,s[j].i,s[j].j,s[j].k);
		  fclose(stdout);
		  return 0;}}
 printf("-1");
 fclose(stdout);
 return 0;}