Cod sursa(job #227391)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 4 decembrie 2008 15:10:22
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<cstdio>

using namespace std;

int a[101],k,i,n,s,sum[1000001],j,l=1;

struct poz{int x,y,z;}p[1000001];
void divide(int s, int d, int&m)
{       int i=s,j=d,pi=0,pj=1;
        while(i<j)
        {       if(sum[i]>sum[j])
                        sum[i]^=sum[j]^=sum[i]^=sum[j],pi^=pj^=pi^=pj,
                        p[i].x^=p[j].x^=p[i].x^=p[j].x,
                        p[i].y^=p[j].y^=p[i].y^=p[j].y,
                        p[i].z^=p[j].z^=p[i].z^=p[j].z;
                i+=pi;j-=pj;
        }
        m=i;
}
void qsort(int s, int d)
{       int m;
        if(s<d)
                divide(s,d,m),
                qsort(s,m-1),
                qsort(m+1,d);
}
int main()
{       register int ok=0,mid,st,dr;
        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=1;j<=n;j++)
                        for(k=1;k<=n;k++)
                                sum[l]=a[i]+a[j]+a[k],
                                p[l].x=i,p[l].y=j,p[l++].z=k;
        qsort(1,l-1);
        for(i=1;i<=l&&!ok;i++)
        {       st=1,dr=l;
                while(st<=dr&&!ok)
                {       mid=(st+dr)/2;
                        if(sum[i]+sum[mid]==s)
                                printf("%d %d %d %d %d %d",a[p[i].x],a[p[i].y],a[p[i].z],a[p[mid].x],a[p[mid].y],a[p[mid].z]),
                                ok=1;
                        else    if(sum[i]+sum[mid]>s)
                                        dr=mid-1;
                                else
                                        st=mid+1;
                }
        }
        if(!ok) printf("-1");
        return 0;
}