Cod sursa(job #2430009)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 12 iunie 2019 13:03:14
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 107;

int t[DIM];

struct Suma
{
    int sum, f1, f2, f3;
};

vector <Suma> v;

bool cmp(Suma a, Suma b)
{
    return a.sum <= b.sum;
}

int main()
{
    int n, s;
    in >> n >> s;

    for(int i = 1; i <= n; i++)
    {
        in >> t[i];
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
            {
                long long sum = t[i] + t[j] + t[k];

                v.push_back(Suma{sum, i, j, k});
            }

    sort(v.begin(), v.end(), cmp);

    for(int i = 0; i < v.size() && v[i].sum * 2 <= s; i++)
    {
        int p = s - v[i].sum;

        int l = i;
        int r = v.size() - 1;

        int pos = -1;

        while(l <= r)
        {
            int mid = (l + r) / 2;

            if(v[mid].sum  > p)
            {
                r = mid - 1;
            }
            else
                if(v[mid].sum < p)
                {
                    l = mid + 1;
                }
                else
                {
                    out << v[i].f1 << ' ' << v[i].f2 << ' ' << v[i].f3 << ' ' << v[mid].f1 << ' ' << v[mid].f2 << ' ' << v[mid].f3 << '\n';
                    return 0;
                }
        }
    }

    out << -1;
}