Cod sursa(job #2407504)

Utilizator teisanumihai84Mihai Teisanu teisanumihai84 Data 16 aprilie 2019 22:07:09
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <algorithm>
#define a first
#define b second
using namespace std;
int n, S, i, j, k, st, dr, mid, v[101], dim1, dim2;
pair <pair <int, int>, pair< int,int> >  s1[1000001];
pair <pair <int, int>, pair< int,int> >  s2[1000001];
int main()
{
    ifstream fin ("loto.in");
    ofstream fout ("loto.out");
    fin>>n>>S;
    for (i=1; i<=n; i++)
        fin>>v[i];
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            for (k=j; k<=n; k++)
            {
                s1[++dim1].a.a=v[i]+v[j]+v[k];
                s1[dim1].a.b=v[i];
                s1[dim1].b.a=v[j];
                s1[dim1].b.b=v[k];
                if (S>=v[i]+v[j]+v[k])
                {
                    s2[++dim2].a.a=S-v[i]-v[j]-v[k];
                    s2[dim2].a.b=v[i];
                    s2[dim2].b.a=v[j];
                    s2[dim2].b.b=v[k];
                }
            }
    sort (s1+1, s1+dim1+1);
    for (i=1; i<=dim2; i++)
    {
        st=1;
        dr=dim1;
        while (st<=dr)
        {
            mid=(st+dr)/2;
                if (s1[mid].a.a==s2[i].a.a)
                {
                    fout<<s1[mid].a.b<<" "<<s1[mid].b.a<<" "<<s1[mid].b.b<<" "<<s2[i].a.b<<" "<<s2[i].b.a<<" "<<s2[i].b.b;
                    return 0;

                }
                else if (s1[mid].a.a>s2[i].a.a)
                    dr=mid-1;
                else
                    st=mid+1;
        }
    }
    fout<<-1;
}