Cod sursa(job #2153052)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 5 martie 2018 22:14:21
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <bits/stdc++.h>
std::ifstream in("loto.in");
std::ofstream out("loto.out");
using namespace std;
 int n , S ;
  const int dimensiunea9a=101;
     int v[dimensiunea9a];
     inline void input()
     {
         in >> n >> S ;
          for( int i =1 ; i <=n ;++i)
                     in >> v[i];
     }

       struct element
       {
           int primu,al_doilea,al_treilea,suma;
       };
   element aux[500005];
         int dim;
         inline void construiesc_ceva()
         {
             for(int i =1; i <=n ;++i)
                   for(int j =1 ; j <=n ;++j)
                            for(int k =1; k<=n ;++k)
             {
                 element e ;
                 e.primu=v[i];
                 e.al_doilea=v[j];
                 e.al_treilea=v[k];
                 e.suma=v[i]+v[j]+v[k];
                  aux[++dim]=e;
             }
         }
         inline bool compare(element i , element j)
         {
             return i.suma<j.suma;
         }

         int caut_binar(int value)
         { int pozitie=-1;
             int left=1,right=dim;
             while(left<=right)
             {
                 int mijloc=(left+right)/2;
                 if(aux[mijloc].suma==value)return mijloc;
                 else if(aux[mijloc].suma<value)left=mijloc+1;
                 else right=mijloc-1;
             }
              return pozitie;
         }



int main()
{input();
construiesc_ceva();
sort(aux+1,aux+dim+1,compare);

                for(int i =1 ; i <= dim ; ++i)
                {
                    int ce_am = aux[i].suma;
                          int pozitie = caut_binar(S-ce_am);
                            if(pozitie!=-1)
                            {
                                out<<aux[i].primu<<" "<<aux[i].al_doilea<<" "<<aux[i].al_treilea<<" "<<aux[pozitie].primu<<" "<<aux[pozitie].al_doilea<<" "<<aux[pozitie].al_treilea;
                                return 0;
                            }
                }
                out<<"-1";
    return 0;
}