Cod sursa(job #2475877)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 17 octombrie 2019 18:31:40
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 101;
const int MOD = 666013;

ifstream fin("loto.in");
ofstream fout("loto.out");

int N, S;
int V[NMAX];

struct hash
{
    int sum;
    int a, b, c;

    bool operator < ( const hash &A ) const
    {
        return sum < A.sum;
    }
};
vector < hash > H[MOD];

void Read()
{
    fin >> N >> S;

    for( int i = 1; i <= N; ++i )
        fin >> V[i];

    sort(V+1, V+N+1 );

    for( int i = 1; i <= N; ++i )
        for( int j = 1; j <= N; ++j )
            for( int k = 1; k <= N; ++k )
            {
                int s = V[i] + V[j] + V[k];
                int mod = s%MOD;

                H[mod].push_back( {s, V[i], V[j], V[k]} );
            }
}

int BS( int x, int lf, int rg, int val )
{
    //cout << lf << ' ' << rg << ' ' << val << '\n';

    if( lf > rg ) return -1;

    int mid = rg - ( rg - lf ) / 2;

    if( H[x][mid].sum == val )return mid;
    if( H[x][mid].sum < val ) return BS( x, lf, mid - 1, val );
    else return BS( x, mid + 1, rg, val );
}
void Loto()
{
    for( int i = 1; i <= N; ++i )
        for( int j = 1; j <= N; ++j )
            for( int k = 1; k <= N; ++k )
            {
                int s = V[i] + V[j] + V[k];
                s = S - s;
                int mod = s%MOD;

                if( H[mod].size() )
                {
                    int pos = BS( mod, 0, H[mod].size()-1, s );

                    if( pos >= 0 )
                    {
                        fout << V[i] << ' ' << V[j] << ' ' << V[k] << ' ' << H[mod][pos].a << ' ' << H[mod][pos].b << ' ' << H[mod][pos].c;
                        return ;
                    }
                }
            }

    fout << -1;
}
int main()
{
    Read();
    Loto();
    return 0;
}