Cod sursa(job #2412342)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 22 aprilie 2019 09:53:03
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

#define N 105

using namespace std;

struct valoare{
    int sum, x, y, z;
}ps[1000005];

int a[N], n, s;
int cnt;

bool cmp(valoare la, valoare lb){
    return la.sum<lb.sum;
}

int cautBin(int val){
    int start = 0, baza = 1;
    for(baza;baza<cnt;baza<<=1);
    for(start;baza;baza>>=1)
        if(start+baza < cnt){
            if(ps[start+baza].sum==val)
                return start+baza;
            if(ps[start+baza].sum<val)
                start+=baza;
        }
    return -1;
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    for(int i = 0; i < n; ++i)
        for(int j = i; j < n; ++j)
            for(int k = j; k < n; ++k){
                int sum = a[i]+a[j]+a[k];
                ps[cnt++]={sum,a[i],a[j],a[k]};
            }

    sort(ps,ps+cnt,cmp);

    for(int i = 0; i < cnt; ++i){
        int r = cautBin(s-ps[i].sum);
        if(r!=-1){
            printf("%d %d %d %d %d %d", ps[i].x,ps[i].y,ps[i].z,
                    ps[r].x, ps[r].y, ps[r].z);
            return 0;
        }
    }

    cout<<-1;

    return 0;
}