Cod sursa(job #2693365)

Utilizator danibaciuBaciu Daniel Mihai danibaciu Data 5 ianuarie 2021 17:17:17
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb

#include <bits/stdc++.h>
#define MOD 1572869

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct item {
    int sum, a, b;
};

vector < item > Hash[MOD];

bool found(int x) {
    int key = x % MOD;
    for(auto& v : Hash[key])
        if(v.sum == x)
            return true;
    return false;
}

void add(int x, int a, int b) {
    if(found(x))
        return;
    int key = x % MOD;
    Hash[key].push_back(item{x, a, b});
}

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];
    for(int i = 1; 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];
                add(sum, a[i], a[j]);
                if(S > sum) {
                    int x = S - sum;
                    if(found(x)) {
                        fout << a[i] << ' ' << a[j] << ' ' << a[k] << ' ';
                        int key = x % MOD;
                        for(auto& v : Hash[key])
                            if(v.sum == x) {
                                fout << v.a << ' ' << v.b << ' ' << v.sum - v.a - v.b;
                                return 0;
                            }
                    }
                }
            }
    fout << -1;
}