Pagini recente » Cod sursa (job #2912648) | Profil EJOI_GREECE | brasov_6_jr | Cod sursa (job #308940) | Cod sursa (job #172684)
Cod sursa(job #172684)
#include<fstream>
using namespace std;
long long sum[1000001][4],l,ll;
void recons_heap(long long i)
{
long long maxim,lef,r;
maxim=i;
lef=2*i;
r=2*i+1;
if (lef<=ll&&sum[lef][0]>sum[maxim][0]) maxim=lef;
if (r<=ll&&sum[r][0]>sum[maxim][0]) maxim=r;
if (maxim!=i)
{
long long aux;
aux=sum[maxim][0];
sum[maxim][0]=sum[i][0];
sum[i][0]=aux;
aux=sum[maxim][1];
sum[maxim][1]=sum[i][1];
sum[i][1]=aux;
aux=sum[maxim][2];
sum[maxim][2]=sum[i][2];
sum[i][2]=aux;
aux=sum[maxim][3];
sum[maxim][3]=sum[i][3];
sum[i][3]=aux;
recons_heap(maxim);
}
}
void cons_heap()
{
long long i;
for (i=ll/2;i>=1;i--) recons_heap(i);
}
void heap_s()
{
long long i;
cons_heap();
for (i=ll;i>=2;i--)
{
long long aux;
aux=sum[1][0];
sum[1][0]=sum[i][0];
sum[i][0]=aux;
aux=sum[1][1];
sum[1][1]=sum[i][1];
sum[i][1]=aux;
aux=sum[1][2];
sum[1][2]=sum[i][2];
sum[i][2]=aux;
aux=sum[1][3];
sum[1][3]=sum[i][3];
sum[i][3]=aux;
ll--;
recons_heap(1);
}
}
int main()
{
long long i,n,s,st[10],k,v[105],j;
ifstream f("loto.in");
ofstream g("loto.out");
f>>n>>s;
for (i=1;i<=n;i++) f>>v[i];
/*k=1;
st[k]=0;
while (k)
{
st[k]++;
if (st[k]<=n)
{
if (k==3)
{
sum[++l][0]=v[st[1]]+v[st[2]]+v[st[3]];
sum[l][1]=v[st[1]];
sum[l][2]=v[st[2]];
sum[l][3]=v[st[3]];
}
else
{
k++;
st[k]=0;
}
}
else k--;
}*/
for (i=1;i<=n; i++)
for (j=i;j<=n;j++)
for (k=j;k<=n;k++)
{
sum[++l][0]=v[i]+v[j]+v[k];
sum[l][1]=v[i];
sum[l][2]=v[j];
sum[l][3]=v[k];
}
ll=l;
heap_s();
long long caut,ok=1,a,b,mij,x[7];
ok=1;
for (i=1;i<=l&&ok;i++)
if (s>=sum[i][0])
{
caut=s-sum[i][0];
a=1;
b=l;
ok=1;
while (a<=b&&ok)
{
mij=(a+b)/2;
if (sum[mij][0]==caut)
{
x[1]=sum[i][1];x[2]=sum[i][2];x[3]=sum[i][3];x[4]=sum[mij][1];x[5]=sum[mij][2];x[6]=sum[mij][3];
long long aux,ca;
do
{
ca=0;
for (j=1;j<6;j++) if (x[j]>x[j+1])
{
aux=x[j];
x[j]=x[j+1];
x[j+1]=aux;
ca=1;
}
} while (ca);
for (j=1;j<=6;j++) g<<x[j]<<' ';
ok=0;
}
if (sum[mij][0]>caut) b=mij-1;
else a = mij+1;
//if (sum[mij][0]<caut) a=mij+1;
}
}
if (ok) g<<"-1\n";
f.close();
g.close();
return 0;
}