Cod sursa(job #3315087)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 12 octombrie 2025 12:31:42
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Triple
{
    int a, b, c;
    long long sum;
};

int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");

    int N;
    long long S;
    f >> N >> S;

    vector<long long> v(N + 1);
    for (int i = 1; i <= N; i++)
    {
        f >> v[i];
    }

    int maxComb = N * (N + 1) * (N + 2) / 6;
    vector<Triple> part1(maxComb + 1);
    vector<Triple> part2(maxComb + 1);

    int idx = 0;

    for (int i = 1; i <= N; i++)
    {
        for (int j = i; j <= N; j++)
        {
            for (int k = j; k <= N; k++)
            {
                idx++;
                part1[idx].a = (int)v[i];
                part1[idx].b = (int)v[j];
                part1[idx].c = (int)v[k];
                part1[idx].sum = v[i] + v[j] + v[k];

                part2[idx] = part1[idx];
            }
        }
    }

    sort(part2.begin() + 1, part2.begin() + idx + 1, [](const Triple &x, const Triple &y)
    {
        return x.sum < y.sum;
    });

    bool found = false;

    for (int i = 1; i <= idx && !found; i++)
    {
        long long need = S - part1[i].sum;

        int st = 1, dr = idx, mid;
        while (st <= dr)
        {
            mid = (st + dr) / 2;
            if (part2[mid].sum == need)
            {
                g << part1[i].a << " " << part1[i].b << " " << part1[i].c << " "
                  << part2[mid].a << " " << part2[mid].b << " " << part2[mid].c;
                found = true;
                break;
            }
            else if (part2[mid].sum < need)
            {
                st = mid + 1;
            }
            else
            {
                dr = mid - 1;
            }
        }
    }

    if (!found)
    {
        g << -1;
    }

    return 0;
}