Cod sursa(job #922322)

Utilizator iarbaCrestez Paul iarba Data 22 martie 2013 08:15:18
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
using namespace std;
long a[1000001],n,aux,kk,p[1000002];
long cauta(int x,int y,int i)
{
    if(x==y){return x;}
    else{
    if(a[(x+y)/2]==kk-a[i]){return ((x+y)/2);}
    else{
        if(a[(x+y)/2]>=kk-a[i]){return cauta(x,(x+y)/2,i);}
        if(a[(x+y)/2]<=kk-a[i]){return cauta((x+y)/2+1,y,i);}
        }
        }
}
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;
//            aux=s[xx][0];s[xx][0]=s[yy][0];s[yy][0]=aux;
//            aux=s[xx][1];s[xx][1]=s[yy][1];s[yy][1]=aux;
//            aux=s[xx][2];s[xx][2]=s[yy][2];s[yy][2]=aux;
            aux=p[xx];p[xx]=p[yy];p[yy]=aux;
            xx++;yy--;
                 }
      }while(xx<=yy);
    if(x<yy){sortare(x,yy);}
    if(xx<y){sortare(xx,y);}
}
int main()
{
    int k,i,j,v[101],p1,p2,sum,cont=0;
    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++){
                sum=v[i]+v[j]+v[k];
                if(sum<kk){a[++cont]=sum;
//                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];
                p[cont]=i*n*n+j*n+k;}
                               }
                           }
                       }
    sortare(0,cont);
    p1=-1;p2=-1;
/*
    for(i=0;i<=cont;i++){
        if(a[i]==a[i-1]){continue;}
        aux=cauta(0,cont,i);
        if(a[aux]+a[i]==kk){p1=i;i=cont+1;p2=aux;}
                           }*/
	aux=1;i=cont;
	while(aux<=i){
		if(a[aux]+a[i]<kk){aux++;}
		if(a[aux]+a[i]>kk){i--;}
		if(a[aux]+a[i]==kk){p1=aux;cont=i;aux=cont;i=1;}
			   }
    if(p1==-1){printf("-1\n");}
    else{p1=p[p1];p2=p[p2];
    for(i=1;i<=3;i++){printf("%ld ",v[p1%n]);p1/=n;}
    for(i=1;i<=3;i++){printf("%ld ",v[p2%n]);p2/=n;}
        }
return 0;
}