Cod sursa(job #904973)

Utilizator iarbaCrestez Paul iarba Data 5 martie 2013 10:08:55
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
using namespace std;
long a[1000001],s[100001][3],k,i,j,n,v[101],p1,p2,aux,kk;
long cauta(int x,int y)
{
	if(x==y){return x;}
	else{
	if(a[(x+y)/2]==k-a[i]){return ((x+y)/2);}
	else{
		if(a[(x+y)/2]>kk-a[i]){return cauta(x,(x+y)/2);}
		if(a[(x+y)/2]<kk-a[i]){return cauta((x+y)/2+1,y);}
		}
		}
} 
void sortare(int x,int y)
{
	int piv=a[(x+y)/2],xx=x,yy=y,aux;
	do{
		while(a[xx]<piv){xx++;}
		while(a[yy]>piv){yy--;}
		if(xx<=yy){
			aux=a[xx];a[xx]=a[yy];a[yy]=aux;xx++;yy--;
				 }
	  }while(xx<=yy);
	if(x<yy){sortare(x,yy);}
	if(xx<y){sortare(xx,y);}
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%ld%ld",&n,&kk);
	for(i=0;i<=n-1;i++){scanf("%ld",&v[i]);}
	for(i=0;i<=n-1;i++){
		for(j=0;j<=n-1;j++){
			for(k=0;k<=n-1;k++){
				a[i*n*n+j*n+k]=v[i]+v[j]+v[k];
				s[i*n*n+j*n+k][0]=v[i];
				s[i*n*n+j*n+k][1]=v[j];
				s[i*n*n+j*n+k][2]=v[k];
							   }
						   }
					   }
	sortare(0,n*n*n-1);
	p1=-1;p2=-1;
	for(i=0;i<=n*n*n-1;i++){
		aux=cauta(0,n*n*n-1);
		if(a[aux]+a[i]==kk){p1=i;i=n*n*n;p2=aux;}
						   }
	if(p1==-1){printf("-1\n");}
	else{printf("%ld %ld %ld %ld %ld %ld\n",s[p1][0],s[p1][1],s[p1][2],s[p2][0],s[p2][1],s[p2][2]);}
return 0;
}