Cod sursa(job #2293141)

Utilizator TooHappyMarchitan Teodor TooHappy Data 30 noiembrie 2018 16:29:29
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("loto.in");
ofstream out("loto.out");

struct triplet {
    int i, j, k;

    triplet(int _i = 0, int _j = 0, int _k = 0) {
        i = _i, j = _j, k = _k;
    }

    friend ostream& operator<<(ostream &out, const triplet &other) {
        out << other.i << " " << other.j << " " << other.k << " ";
        return out;
    }
};

int n, s;
vector< int > sums, v;
unordered_map< int, triplet > uMep;

bool bSearch(int left, int right, int val) {
    while(left <= right) {
        int mid = (left + right) / 2;

        if(sums[mid] == val) {
            return true;
        }

        if(sums[mid] < val) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);
    
    in >> n >> s;

    v.resize(n);
    for(auto &it: v) {
        in >> it;
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            for(int k = i; k <= j; ++k) {
                int tempSum = v[i] + v[j] + v[k];
                sums.push_back(tempSum);
                uMep[tempSum] = triplet(v[i], v[j], v[k]);
            }
        }
    }   
    sort(sums.begin(), sums.end());
    
    for(int i = 0; i < (int)sums.size() - 1; ++i) {
        if(bSearch(i + 1, (int)sums.size(), s - sums[i]) == true) {
            out << uMep[sums[i]] << uMep[s - sums[i]];
            exit(0);
        }
    }

    out << "-1\n";
 
    in.close(); out.close();
 
    return 0;
}