Pagini recente » Cod sursa (job #392075) | Cod sursa (job #1261616) | Cod sursa (job #213777) | Cod sursa (job #1983701) | Cod sursa (job #420594)
Cod sursa(job #420594)
#include<fstream>
#include<iostream>
using namespace std;
int b[1000100],a[110],h[1000100],s1[1000100],s2[1000100],s3[1000100];
void qs(int i, int j)
{
int s=i,d=j,aux,piv=h[(i+j)>>1];
while(s<=d)
{
while(b[h[s]]<b[piv])
s++;
while(b[h[d]]>b[piv])
d--;
if(s<=d)
{
aux=h[s];
h[s]=h[d];
h[d]=aux;
s++;
d--;
}
}
if(s<j)
qs(s,j);
if(i<d)
qs(i,d);
}
int main()
{
int n,s,k=0,i,j,t,l=1,x,S,ok=0,a1,a2;
ifstream f("loto.in");
ofstream g("loto.out");
f>>n>>S;
for(i=1;i<=n;i++)
f>>a[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(t=1;t<=n;t++)
{
b[++k]=a[i]+a[j]+a[t];
h[k]=k;
s1[k]=i;
s2[k]=j;
s3[k]=t;
}
qs(1,k);
while(l<k)
l<<=1;
for(i=1;i<=k&!ok&&b[h[i]]<S;i++)
{
x=S-b[h[i]];
s=l;
j=0;
while(s&&!ok)
{
if(j+s<=k&&b[h[j+s]]<=x)
j+=s;
if(b[h[j]]==x)
{
a1=h[i];
a2=h[j];
ok=1;
}
s>>=1;
}
}
if(!ok)
g<<"-1";
else
g<<a[s1[a1]]<<' '<<a[s2[a1]]<<' '<<a[s3[a1]]<<' '<<a[s1[a2]]<<' '<<a[s2[a2]]<<' '<<a[s3[a2]];
return 0;
}