Cod sursa(job #345351)

Utilizator MKLOLDragos Ristache MKLOL Data 2 septembrie 2009 17:16:05
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<algorithm>
using namespace std;
struct pro{
int x,a,b,c;} a[100*100*100+1];
int v[101],Cat,ifin,jfin,N,z=1,S;
inline void inter(int &ww,int &qq)
{
    int aux;
    aux=ww;
    ww=qq;
    qq=aux;
}

inline void qsort(int p,int r)
{
int st=p,dr=r,piv=a[(st+dr)/2].x;
while(st<dr)
{
while(a[st].x<piv) ++st;
while(a[dr].x>piv) --dr;
if(dr>=st)
{
    inter(a[dr].a,a[st].a);
    inter(a[dr].b,a[st].b);
    inter(a[dr].c,a[st].c);
    inter(a[dr].x,a[st].x);
++st;
--dr;
}
}
if(st<r)
qsort(st,r);
if(dr>p)
qsort(p,dr);

}
int main()
{int st,dr,mid;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
scanf("%d%d",&N,&S);
for(int i=1;i<=N;++i)
scanf("%d",&v[i]);

for(int i=1;i<=N;++i)
    for(int j=1;j<=N;++j)
        for(int o=1;o<=N;++o)
            {
            a[z].a=v[i];
            a[z].b=v[j];
            a[z].c=v[o];
            a[z].x=v[o]+v[i]+v[j];
            ++z;
            }
qsort(1,z-1);
for(int i=1;i<=z-1&&a[i].x<=S-a[1].x;++i)
{

Cat=S-a[i].x;
st=1; dr=z-1;
if(a[i].x!=a[i-1].x)
while(st<=dr)
{
    mid=(st+dr)/2;
    if(a[mid].x==Cat)
    {   st=dr*2;
        ifin=i;
        jfin=mid;
        i=z+z;
    }
    if(a[mid].x>Cat)
    dr=mid-1;
    if(a[mid].x<Cat)
    st=mid+1;
}


}
if(ifin!=0&&jfin!=0)
{
printf("%d %d %d ",a[ifin].a,a[ifin].b,a[ifin].c);

printf("%d %d %d",a[jfin].a,a[jfin].b,a[jfin].c);
}
else printf("-1");

}