Cod sursa(job #3148990)

Utilizator PetraPetra Hedesiu Petra Data 5 septembrie 2023 17:22:26
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define MOD 666013

using namespace std;

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

int n, s, mx;
struct p_entry {
    int sum, a, b, c;
};

//inline bool operator< (p_entry &x, p_entry &y)
//{
//    return (x.sum < y.sum);
//}
//
//vector<p_entry> p;
//
//int cautare_binara(int x, int st, int dr)
//{
//    if (st > dr) return -1;
//    int mijl = (st + dr) / 2;
//    if (p[mijl].sum == x) return mijl;
//    if (p[mijl].sum > x) return cautare_binara(x, 0, mijl - 1);
//    if (p[mijl].sum < x) return cautare_binara(x, mijl + 1, dr);
//}

vector<int> v;
vector<p_entry> hashh[MOD];

void add(p_entry element)
{
    int x = element.sum;
    hashh[x%MOD].push_back(element);
}

void remove(p_entry element)
{
    int x = element.sum;
    for (int i = 0; i < hashh[x%MOD].size(); i++)
    {
        if (hashh[x%MOD][i].sum == x)
        {
            hashh[x%MOD][i] = hashh[x%MOD][hashh[x%MOD].size()-1];
            hashh[x%MOD].pop_back();
            return;
        }
    }
}

int exists(p_entry element)
{
    int x = element.sum;
    for (int i= 0 ; i < hashh[x%MOD].size(); i++)
        if (hashh[x%MOD][i].sum == x)
            return 1;
    return 0;
}

int main()
{
    fin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        int x;
        fin >> x;
        mx = max(mx, x);
        v.push_back(x);
    }
    if (6 * mx < s)
    {
        fout << -1;
        return 0;
    }
    if (6 * mx == s)
    {
        for (int i = 0; i < 6; i++)
            fout << mx << " ";
        return 0;
    }

    for (int i = 0; i < v.size(); i++)
        for (int j = 0; j < v.size(); j++)
            for (int k = 0; k < v.size(); k++)
                add({v[i]+v[j]+v[k], v[i], v[j], v[k]});

    for (int i = 0; i < MOD; i++)
    {
        if (hashh[i%MOD].size()==0) continue;

        for (int j = 0; j < hashh[i%MOD].size(); j++)
        {
            p_entry el1 = hashh[i%MOD][j];
            if (hashh[s-el1.sum].size()==0) continue;
            p_entry el2 = hashh[s-el1.sum][0];
            fout << el1.a << " " << el1.b << " " << el1.c << " " <<
                    el2.a << " " << el2.b << " " << el2.c;
            return 0;
        }
    }
    fout << -1;
    return 0;
}