Cod sursa(job #1402391)

Utilizator andreey_047Andrei Maxim andreey_047 Data 26 martie 2015 15:57:35
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <algorithm>
#define nmin 103
#define MASK 65535
#define nmax 1000003
using namespace std;
int a[nmin],n,s,m,cnt[MASK+10],b[nmax],t[nmax],c[nmax];
struct Coord{
 int x,y,z,sum;
};
Coord aux[nmax];
void radix()
{
    int grad,i;
    for(grad=0;grad<=16;grad+=16)
    {
        for(i=0;i<=MASK;++i)
            cnt[i]=0;
        for(i=1;i<=m;++i)
        {
            b[i]=((t[i]>>grad)&MASK);
            ++cnt[b[i]];
        }
        for(i=1;i<=MASK;++i)
            cnt[i]+=cnt[i-1];
        for(i=m;i;--i){
            c[cnt[b[i]]--]=t[i];
            }
        for(i=1;i<=m;++i)
                t[i]=c[i];
    }
}
inline void Preprocess(){
 int i,j,k;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
     for(k=1;k<=n;k++){
            t[++m]=a[i]+a[j]+a[k];
            aux[m].sum=a[i]+a[j]+a[k];
            aux[m].x=a[i];
            aux[m].y=a[j];
            aux[m].z=a[k];
      }
  radix();
}
inline int Binsearch(int key){
 int mij,l,r;
 l=1;r=m;
 while(l<=r){
    mij=(l+r)/2;
    if(t[mij] == key){
        for(int i=1;i<=m;++i)
            if(aux[i].sum == key)return i;
    }
    else if(t[mij] > key)r=mij-1;
    else l=mij+1;
 }
 return -1;
}
inline void DERIVEAZA(){
 int i,x,b,ok,j;
  if(t[m]*1LL*6 < s)
 for(i=m;i>0;--i){
   x=Binsearch(s-t[i]);
   if(x>0){
          ok=1;
        for(j=1;j<=m&&ok;++j)
         if(aux[j].sum == t[i]){ok=0;b=j;}
    printf("%d %d %d %d %d %d\n",aux[b].x,aux[b].y,aux[b].z,aux[x].x,aux[x].y,aux[x].z);
    return;
   }
 }
 printf("-1\n");
}
int main(){
    int i;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d\n",&n,&s);
    for(i=1;i<=n;i++)
        scanf("%d ",&a[i]);
     Preprocess();
     DERIVEAZA();
    return 0;
}