Cod sursa(job #345347)

Utilizator MKLOLDragos Ristache MKLOL Data 2 septembrie 2009 17:11:12
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<algorithm>
using namespace std;
struct pro{
int x;
char 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 inter(char &ww,char &qq)
{
    char 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=i;
            a[z].b=j;
            a[z].c=o;
            a[z].x=v[o]+v[i]+v[j];
            ++z;
            }
qsort(1,z-1);
for(int i=1;i<z;++i)
{
    Cat=S-a[i].x;
    int ret = 0;
    for (int ii=1<<19;ii>0;ii/=2)
        if (ret + ii <= z-1)
        if (a[ret+ii].x <= Cat)
            ret += ii;

    if (ret != i && a[ret].x == Cat)
    {
        printf("%d %d %d ",v[a[ret].a],v[a[ret].b],v[a[ret].c]);

        printf("%d %d %d",v[a[i].a],v[a[i].b],v[a[i].c]);
        return 0;
    }
    if (ret < i)
        break;
}
    printf("-1");

    return 0;
}