Pagini recente » Cod sursa (job #1668334) | Cod sursa (job #3149187) | Cod sursa (job #2624992) | Cod sursa (job #3134041) | Cod sursa (job #420599)
Cod sursa(job #420599)
#include<fstream>
using namespace std;
int b[1000100],a[110],h[1000100],s1[1000100],s2[1000100],s3[1000100],hh[110];
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);
}
void qsmic(int i, int j)
{
int s=i,d=j,aux,piv=hh[(i+j)>>1];
while(s<=d)
{
while(b[hh[s]]<b[piv])
s++;
while(b[hh[d]]>b[piv])
d--;
if(s<=d)
{
aux=hh[s];
hh[s]=hh[d];
hh[d]=aux;
s++;
d--;
}
}
if(s<j)
qsmic(s,j);
if(i<d)
qsmic(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];
hh[i]=i;
}
qsmic(1,n);
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
for(t=j;t<=n;t++)
{
b[++k]=a[hh[i]]+a[hh[j]]+a[hh[t]];
h[k]=k;
s1[k]=hh[i];
s2[k]=hh[j];
s3[k]=hh[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;
}