Cod sursa(job #2472499)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 12 octombrie 2019 15:14:14
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 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;
}