Cod sursa(job #2382508)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 18 martie 2019 14:04:40
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda cautare-binara Marime 1.9 kb

#include <bits/stdc++.h>
using namespace std;
ifstream in ("loto.in");
ofstream out ("loto.out");
int v[1000001],raspuns [7];
struct suma{int x1,x2,x3,s;} sume[1000001];
bool verfmutare(suma a,suma b)
{
    return a.s<b.s;
}
int main()
{
    int n,s,cnt=1;
    in>>n>>s;
    for (int i=1;i<=n;++i)
        in>>v[i];
    for (int i=1;i<=n;++i)
        for (int k=i;k<=n;++k)
            for (int j=k;j<=n;++j)
                {
                    sume[cnt].s=v[i]+v[j]+v[k];
                    sume[cnt].x1=v[i];
                    sume[cnt].x2=v[k];
                    sume[cnt].x3=v[j];
                    ++cnt;
                }
    sort(sume+1,sume+cnt,verfmutare);
    for (int i=1;i<=n;++i)
        for (int k=i;k<=n;++k)
            for (int j=k;j<=n;++j)
            {
                int s1=s-(v[i]+v[j]+v[k]);
                int l=1,r=cnt,ok=0,ok1=0;
                while (l<=r && !ok)
                {
                    int mid=(l+r)/2;
                    if (sume[mid].s==s1)
                    {
                        ok=mid;
                        ok1=1;
                    }
                    if (v[mid]<s1)
                        l=mid+1;
                    else
                        r=mid-1;
                }
                if (ok1==1)
                {
                    int c1,c2,c3;
                    c1=sume[ok].x1;
                    c2=sume[ok].x2;
                    c3=sume[ok].x3;
                    int ver=c1+c2+c3+v[i]+v[j]+v[k];
                    if (ver==s)
                    {
                        raspuns[1]=v[i],raspuns[2]=v[j],raspuns[3]=v[k],raspuns[4]=c1,raspuns[5]=c2,raspuns[6]=c3;
                        for (int i=1;i<=6;++i)
                            out<<raspuns[i]<<' ';
                        return 0;
                    }
                }
            }
    out << -1;
    return 0;
}