Cod sursa(job #2932275)

Utilizator Luka77Anastase Luca George Luka77 Data 2 noiembrie 2022 15:08:50
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 105;
int n, s, arr[NMAX], maxi = 0;
struct QUATRO{
    int f1, f2, f3, f4;
};
vector<QUATRO>sums;

inline int b_search(int target)
{
    int st = 0, dr = sums.size();
    while(st < dr)
    {
        int mid = (st + dr)/2;
        if(sums[mid].f1 == target)
            return mid;
        if(sums[mid].f1 < target)
            st = mid + 1;
        if(sums[mid].f1 > target)
            dr = mid - 1;
    }
    return 0;
}

inline bool comp(QUATRO x, QUATRO y)
{
    return x.f1 < y.f1;
}

inline void solve()
{
    if(maxi*6 < s)
    {
        fout << -1;
        return;
    }
    sort(arr+1, arr+n+1);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                sums.push_back({arr[i] + arr[j] + arr[k], arr[i], arr[j], arr[k]});
            }
        }
    }
    sort(sums.begin(), sums.end(), comp);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                int c = b_search(s- (arr[i] + arr[j] +arr[k]));
                if(c)
                {
                    vector<int>ans;
                    ans.push_back(arr[i]);
                    ans.push_back(arr[j]);
                    ans.push_back(arr[k]);
                    ans.push_back(sums[c].f2);
                    ans.push_back(sums[c].f3);
                    ans.push_back(sums[c].f4);
                    sort(ans.begin(), ans.end());
                    for(auto x : ans)
                        fout << x << ' ';
                    return;
                }
            }
        }
    }
    fout << -1;
}

int main()
{
    fin >> n >> s;
    for(int i=1;i<=n;++i)
        fin >> arr[i], maxi = max(maxi, arr[i]);
    solve();
}