Cod sursa(job #2430019)

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

using namespace std;

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

const int DIM = 107;
const int DIM2 = 1e6 + 7;

int t[DIM];

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

Suma v[DIM2];

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];
    }

    int n2 = 0;

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

                n2++;

                v[n2].sum = sum;
                v[n2].f1 = t[i];
                v[n2].f2 = t[j];
                v[n2].f3 = t[k];

            }

    sort(v + 1, v + 1 + n2, cmp);

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

        int l = i;
        int r = n2;

        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;
}