Cod sursa(job #165303)

Utilizator nimeniaPaul Grigoras nimenia Data 25 martie 2008 20:16:52
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>

long v[105],n,ns=1;
long a[1000020];
long drum[1000020],drum_aux;
int auxxx[10];

long poz(long li,long ls){
	long i=li,j=ls,t;int mod=1;
	while (i<j){
		  if (a[i]>a[j]){
			 t=a[i],a[i]=a[j],a[j]=t;
			 t=drum[i],drum[i]=drum[j],drum[j]=t;
			 mod=(mod+1)%2;
			 }
		  if (mod==0) i++;
		  else j--;
		  }
	return i;

}

void qsort(long li, long ls){
	if (li<ls){
		long k=poz(li,ls);
		qsort(li,k-1);
		qsort(k+1,ls);
	}
}



/*
long part(long l,long r){
     long p,i,j,t;
     p=a[r];
     j=l-1;
     for (i=l;i<=r;i++) 
         if (a[i]<=p) {j++; t=a[j],a[j]=a[i],a[i]=t,t=drum[j],drum[j]=drum[i],drum[i]=t;}
     return j;
}
void qsort(long l,long r){
     long poz;
     poz=part(l,r);
     if(l<poz-1) qsort(l,poz-1);
     if(r>poz+1) qsort(poz+1,r);
}*/


int gasit(long ax){
   long li=1,ls=ns,m;
   while (li<=ls){
	m=(li+ls)/2;
	if (ax>a[m]) li=m+1;
	else if (ax<a[m]) ls=m-1;
	else if (ax==a[m]) return m;
   }
   return 0;

}



int main(){
	long j,k,q,aux,s;
	freopen ("loto.in", "r",stdin);
	freopen ("loto.out","w",stdout) ;
	scanf("%ld%ld",&n,&s);
	long i;
	for(i=1;i<=n;i++) scanf("%ld",v+i);
	for(i=1;i<=n;i++)for(j=i;j<=n;j++)for(q=j;q<=n;q++)a[ns++]=v[i]+v[j]+v[q],drum[ns-1]=i+j*100+q*10000;
	ns--;
	qsort(1,ns);


    v[0]=v[n];
	int gata=0;
	for (i=1;i<=ns && !gata;i++)
		if (a[i]!=a[i-1]){
			k=gasit(s-a[i]);
			if (k)
				{gata=1;
				 drum_aux=drum[i];
		         for (j=0;j<3;j++) auxxx[j]=drum[i]%100, drum[i]/=100;
				 drum[i]=drum_aux;
 		         for (j=3;j<6;j++) auxxx[j]=drum[k]%100, drum[k]/=100;
                 for(j=0;j<6;j++) printf("%ld ",v[auxxx[j]]);
				}

		}
	if (!gata) printf("-1");

	return 0;
    
    
                     
    
}