Cod sursa(job #1402353)

Utilizator andreey_047Andrei Maxim andreey_047 Data 26 martie 2015 15:15:07
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <algorithm>
#define nmin 103
#define nmax 1000003
using namespace std;
int a[nmin],n,s,m;
struct Coord{
 int x,y,z,sum;
};
Coord t[nmax];
inline bool cmp(const Coord A,const Coord B){
 return A.sum < B.sum;
}
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].sum=a[i]+a[j]+a[k];
            t[m].x=a[i];
            t[m].y=a[j];
            t[m].z=a[k];
      }
  sort(t+1,t+m+1,cmp);
}
inline int Binsearch(int key){
 int mij,l,r;
 l=1;r=m;
 while(l<=r){
    mij=(l+r)/2;
    if(t[mij].sum == key)return mij;
    else if(t[mij].sum > key)r=mij-1;
    else l=mij+1;
 }
 return -1;
}
inline void DERIVEAZA(){
 int i,x;
 for(i=m;i>0;--i){
   x=Binsearch(s-t[i].sum);
   if(x>0){
    printf("%d %d %d %d %d %d\n",t[i].x,t[i].y,t[i].z,t[x].x,t[x].y,t[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;
}