Cod sursa(job #2661576)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 octombrie 2020 12:11:40
Problema Loto Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
	
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("loto.in");
ofstream fout("loto.out");
 
struct item {
    int sum, a, b;

    bool operator < (const item& A) const {
        return sum < A.sum;
    }
};
 
int main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    int N, S;
    fin >> N >> S;
    vector < int > a(N + 1);
    for(int i = 1; i <= N; ++i)
        fin >> a[i];
    vector < item > v;
    v.push_back(item{0, 0, 0});
    for(int i = 1; i <= N; ++i)
        for(int j = i; j <= N; ++j)
            for(int k = j; k <= N; ++k) 
                v.push_back(item{a[i] + a[j] + a[k], a[i], a[j]});
    sort(v.begin() + 1, v.end());
    int M = v.size() - 1;
    for(int i = 1; i <= M; ++i) {
        int val = S - v[i].sum;
        if(val <= 0)
            continue;
        int st = 1, dr = N;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(v[mid].sum == val) {
                fout << v[i].a << ' ' << v[i].b << ' ' << v[i].sum - v[i].a - v[i].b << ' ' << v[mid].a << ' ' << v[mid].b << ' ' << v[mid].sum - v[mid].a - v[mid].b;
                return 0;
            }
            else
                if(v[mid].sum < val)
                    st = mid + 1;
            else 
                dr = mid - 1;
        }
    }
    fout << -1;
}