Cod sursa(job #140769)
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
int v,v1,v2,v3;
};
ceva b[1000005];
char ver[50000005];
int a[105],nr;
void heapsort(long n)
{
long i,j,k;
ceva aux;
for (i=1; i<=n; i++)
{
j=i;
while (j/2!=0&&b[j/2].v<b[j].v)
{
aux=b[j/2];
b[j/2]=b[j];
b[j]=aux;
j=j/2;
}
}
i=n;
while (i>1)
{
aux=b[1];
b[1]=b[i];
b[i]=aux;
i--; j=1;
while (j>0)
{
k=2*j;
if (k>i) break;
if (k+1<=i&&b[k+1].v>b[k].v) k++;
if (b[j].v>b[k].v) break;
aux=b[j];
b[j]=b[k];
b[k]=aux;
j=k;
}
}
}
int compare( const void* a, const void* b )
{
ceva* arg1 = (ceva*) a;
ceva* arg2 = (ceva*) b;
if( arg1->v < arg2->v )
return -1;
else
if( arg1->v == arg2->v )
return 0;
else
return 1;
}
int binary_search(int val)
{
int i, step;
for (step = 1; step <= nr; step <<= 1);
for (i = 1; step; step >>= 1)
if (i + step <= nr && b[i + step].v <= val)
i += step;
if (b[i].v==val)
return i;
else
return -1;
}
int cauta(int x)
{
int u=1,p=nr,m;
while (u<p)
{
m=(u+p)/2;
if (b[m].v==x)
return m;
if (b[m].v<x)
u=m+1;
if (b[m].v>=x)
p=m-1;
}
if (b[u].v==x)
return u;
else
return -1;
}
int main()
{
FILE *in,*out;
int n,s,i,j,j2,x;
in=fopen("loto.in","r");
out=fopen("loto.out","w");
fscanf(in,"%d%d",&n,&s);
for (i=1;i<=n;i++)
{
fscanf(in,"%d",&a[i]);
}
for (i=1;i<=n;i++)
for (j=i;j<=n;j++)
for (j2=j;j2<=n;j2++)
{
nr++;
b[nr].v=a[i]+a[j]+a[j2];
b[nr].v1=a[i];
b[nr].v2=a[j];
b[nr].v3=a[j2];
if (b[nr].v<50000000)
ver[b[nr].v]++;
if (b[nr].v<50000000)
if (ver[b[nr].v]>1)
nr--;
if (b[nr].v>s)
nr--;
}
//qsort(b+1,nr,sizeof(b[1]),compare);
heapsort(nr);
for (i=1;i<=nr;i++)
{
if (s-b[i].v<=b[i-1].v)
break;
x=binary_search(s-b[i].v);
if (x!=-1)
{
fprintf(out,"%d %d %d %d %d %d",b[i].v1,b[i].v2,b[i].v3,b[x].v1,b[x].v2,b[x].v3);
fclose(in);
fclose(out);
return 0;
}
}
fprintf(out,"-1\n");
fclose(in);
fclose(out);
return 0;
}