Cod sursa(job #2380921)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 15 martie 2019 17:39:17
Problema Loto Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define FILE_NAME "loto"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

constexpr int HASH = 1000037;
constexpr int MAX_DIM = 100 + 4;
struct ticket
{
    int sum;
    int x, y, z;
    ticket(int _x = 0, int _y = 0, int _z = 0)
    {
        x = _x, y = _y, z = _z;
        sum = x + y + z;
    }
};
vector < ticket > halfTicket;
int Nums[MAX_DIM];
int N, S, K;

bool operator<(ticket &a, ticket &b)
{
    return a.sum < b.sum;
}

int main()
{
    in >> N >> S;
    for(int i = 0; i < N; ++i)
        in >> Nums[i];

    halfTicket.resize(N*N*N);

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            for(int k = 0; k < N; ++k)
                halfTicket[K++] = ticket(Nums[i], Nums[j], Nums[k]);

    sort(halfTicket.begin(), halfTicket.end());

    for(auto luckyTicket : halfTicket)
    {
        int need = S - luckyTicket.sum;

        int found = -1;
        int st = 0, dr = K-1;
        while(st <= dr)
        {
            int m = st + ((dr-st)>>1);
            if(halfTicket[m].sum == need)
            {
                found = m;
                break;
            }
            else if(halfTicket[m].sum < need)
                st = m + 1;
            else
                dr = m - 1;
        }

        if(found != -1)
        {
            out << luckyTicket.x << ' ' << luckyTicket.y << ' ' << luckyTicket.z << ' '
                << halfTicket[found].x << ' ' << halfTicket[found].y << ' ' << halfTicket[found].z << '\n';
            return 0;
        }
    }

    out << "-1\n";
    return 0;
}