Cod sursa(job #194427)

Utilizator DjSefuWrong name DjSefu Data 10 iunie 2008 16:45:55
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include<stdio.h>
#include<string.h>
FILE *f=fopen("loto.in","r"),
     *g=fopen("loto.out","w");
int i,j,n,k,q[107],v,count[1024],ind[1024],n2,s,v2;
struct nod
{ int v;
  int a;
} a[1000007],b[1000007],c[10007],d[10007];
int find(int v)
{ int left=1;
  int right=k;
  int m=0;
  while(left<=right) { m=(left+right)/2;
                       if(v==b[m].v) return m;
                       else if(v>b[m].v) left=m+1;
                       else right=m-1;
                     }
  return -1;
}
int find2(int k)
{ int left=1;
  int right=v;
  int m=0;
  while(left<=right) { m=(left+right)/2;
                       if(k==d[m].v) return m;
                       else if(k>d[m].v) left=m+1;
                       else right=m-1;
                     }
  return -1;
}
void afis(int x,int y)
{ x=find(x);
  y=find(y);
  fprintf(g,"%d %d ",b[x].a,b[y].a);
  x=b[x].v-b[x].a;
  x=find2(x);
  y=b[y].v-b[y].a;
  y=find2(y);
  fprintf(g,"%d %d %d %d\n",d[x].a,d[y].a,d[x].v-d[x].a,d[y].v-d[y].a);
}
  
void rad(nod *a,nod *b,int byte,int &n)
{ memset(count,0,sizeof(count));
  int i;
  for(i=1;i<=n;++i) ++count[(a[i].v>>byte)&1023];
  ind[0]=1;
  for(i=1;i<1024;++i) ind[i]=ind[i-1]+count[i-1];
  for(i=1;i<=n;++i) b[ind[(a[i].v>>byte)&1023]++]=a[i];
}
void radix(nod *a,int n)
{ rad(a,b,0,n);
  rad(b,a,10,n);
  rad(a,b,20,n);
  rad(b,a,30,n);
}
int main()
{ fscanf(f,"%d %d",&n,&s);
  for(i=1;i<=n;++i) fscanf(f,"%d",&q[i]);
  for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[++v].v=q[i]+q[j];
                                       c[v].a=q[j];
                                     }
  v=0;
  radix(c,n*n);
  memset(d,0,sizeof(d));
  v=0;
  d[0].v=-1;
  for(i=1;i<=n*n;++i) if(c[i].v!=d[v].v) d[++v]=c[i];
  v2=0;
  for(i=1;i<=n;++i) for(j=1;j<=n;++j) for(k=1;k<=n;++k) a[++v2].v=q[i]+q[j]+q[k],a[v2].a=q[k];
  radix(a,n*n*n);
  memset(b,0,sizeof(b));
  k=0;
  b[0].v=-1;
  
  for(i=1;i<=n*n*n;++i) if(a[i].v!=b[k].v) b[++k]=a[i];
  v2=s/2;
  for(i=1;i<=k&&b[i].v<=v2;++i) if(find(s-b[i].v)>0) { afis(b[i].v,s-b[i].v);
                                                      fclose(f);
                                                      fclose(g);
                                                      return 0;
                                                    }
  fprintf(g,"-1\n");
  fclose(f);
  fclose(g);
  return 0;
}