Pagini recente » Cod sursa (job #61114) | Cod sursa (job #63899) | Cod sursa (job #2080985) | Cod sursa (job #3178466) | Cod sursa (job #182676)
Cod sursa(job #182676)
using namespace std;
#include <cstdio>
#include <algorithm>
#include <string>
int a[101], x[1000001/3],n, S;
int N;
int b[1000001/3];
inline void afis(int S)
{
int i,j,k;
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
for(k=j;k<=n;++k)
if(a[i]+a[j]+a[k]==S)
{
printf("%d %d %d ", a[i],a[j],a[k]);
return;
}
}
inline int bsearch(int v)
{
int i, cnt;
for(i=1, cnt=(1<<20); cnt; cnt>>=1)
if(i+cnt<=N)
if(x[i+cnt]<=v) i+=cnt;
if(x[i]==v)return 1;
return 0;
}
inline int rad(int n,int byte, int a[], int b[])
{
int count[1024], index[1024];
memset(count, 0, sizeof(count));
int i;
for(i=1;i<=N;++i) ++count[(a[i]>>byte)&1023];
index[0]=1;
for(i=1;i<1024;++i) index[i]=index[i-1]+count[i-1];
for(i=1;i<=N;++i) b[index[(a[i]>>byte)&1023]++]=a[i];
}
inline void radix()
{
rad(N, 0, x, b);
rad(N, 10, b, x);
rad(N, 20, x, b);
for(int i=1;i<=N;++i) x[i]=b[i];
}
int main()
{
freopen("loto.in","r",stdin);
freopen("loto.out","w",stdout);
scanf("%d %d\n", &n, &S);
int i,j,k;
for(i=1;i<=n;++i) scanf("%d ", &a[i]);
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
for(k=j;k<=n;++k)
x[++N]=a[i]+a[j]+a[k];
// sort(x+1,x+N+1);
radix();
for(i=1;i<=N && x[i]<=S;++i)
if(bsearch(S-x[i]))
{
afis(S-x[i]);
afis(x[i]);
return 0;
}
/*
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
if(binary_search(x+1,x+N+1, S-a[i]-a[j]-a[k]))
{
printf("%d %d %d ", a[i], a[j], a[k]);
afis(S-a[i]-a[j]-a[k]);
return 0;
}
*/
printf("-1\n");
return 0;
}