Cod sursa(job #2475869)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 17 octombrie 2019 18:20:42
Problema Loto Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 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];

vector < int > 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 );
            }
}

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

    if( lf >= rg ) return H[x][lf];

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

    if( H[x][mid] == val )return mid;
    if( H[x][mid] < 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( H[mod][pos] == s )
                    {
                        fout << V[i] << ' ' << V[j] << ' ' << V[k] << ' ';

                        for( int i = 1; i <= N; ++i )
                            for( int j = 1; j <= N; ++j )
                                for( int k = 1; k <= N; ++k )
                                {
                                    if( (V[i] + V[j] + V[k]) == s )
                                    {
                                        fout << V[i] << ' ' << V[j] << ' ' << V[k] << '\n';
                                        return;
                                    }
                                }

                    }
                }
            }

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