Cod sursa(job #2747346)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 29 aprilie 2021 00:43:20
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream fin( "loto.in" );
ofstream fout( "loto.out" );
 
const int MOD = 666013;
const int NMAX = 102;
 
int N, S;
struct h
{
    int val;
    int a, b, c;
 
};
vector <h> Hash[666013];
vector <int> V( NMAX );
 
void Read()
{
    fin >> N >> S;
 
    for( int i = 1; i <= N; ++i )
      fin >> V[i];
}
 
void Hash_add( const int & A, const int & v1, const int & v2, const int & v3 )
{
    int mod = A % MOD;
 
    Hash[mod].push_back( { A, v1, v2, v3 } );
}
 
int Binsearch( const int & mod, int lf, int rg, const int & V )
{
    if( lf > rg ) return -1;
 
    int mid = lf + ( rg - lf ) / 2;
 
    if( Hash[mod][mid].val == V ) return mid;
    if( Hash[mod][mid].val > V ) return Binsearch( mod, lf, mid - 1, V );
    Binsearch( mod, mid + 1, rg, V );
}
 
h* Hash_check( const int & V )
{
    int mod = V % MOD;
 
    int p = Binsearch( mod, 0, Hash[mod].size() - 1, V );
 
    if( p >= 0 ) return &Hash[mod][p];
    else return NULL;
}
 
void Do()
{
    for( int i = 1; i <= N; ++i )
      for( int j = i; j <= N; ++j )
        for( int k = j; k <= N; ++k )
          if( V[i] + V[j] + V[k] <= S )
            Hash_add( S - V[i] - V[j] - V[k], V[i], V[j], V[k] );
 
    bool found = false;
 
    for( int i = 1; i <= N && !found; ++i )
      for( int j = i; j <= N && !found; ++j )
        for( int k = j; k <= N && !found; ++k )
          if( Hash_check( V[i] + V[j] + V[k] ) )
          {
             h *p = Hash_check( V[i] + V[j] + V[k] );
 
             fout << V[i] << ' ' << V[j] << ' ' << V[k] << ' ' << p -> a << ' ' << p -> b << ' ' << p -> c << '\n';
 
             found = true;
          }
 
    if( !found ) fout << "-1\n";
}
 
int main()
{
    Read();
    Do();
 
    fin.close();
    fout.close();
 
    return 0;
}