Cod sursa(job #2670190)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 9 noiembrie 2020 12:58:26
Problema Loto Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <queue>

#define N 101
using namespace std;

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

int n, S, nrSecv, el, gasit, a, b, c;
unordered_map<int, priority_queue<int> > m;////CodSecventa-multimeELemente(maxim  3 elemente) 
unordered_map<int, priority_queue<int>> frecv;///suma-CodSecventa
vector < vector < pair <int, int> > > liste(7, vector<pair<int, int>>());///suma-CodSecventa
 
void afisare(int a, int b);

int main() {
    fin >> n >> S;
    for (int i = 1; i <= n; ++i) {
        fin >> el;
        m[nrSecv].push(el);///la nrSecv se gaseste secventa ...
        liste[1].push_back({ el, nrSecv++ });
    }

    el = 2;
    while (el <= 3) {
        for (int i = 0; i < liste[el - 1].size(); ++i) {
            for (int j = 0; j < liste[1].size(); ++j) {

                a = liste[el - 1][i].first;
                b = liste[1][j].first;
                c = a + b;

                if (c <= S) {
                    frecv[c].push(nrSecv - 1);

                    m[nrSecv] = m[liste[el - 1][i].second];///la nrSecv se gaseste secventa ...
                    m[nrSecv].push(b);

                    liste[el].push_back({ c, nrSecv++ });

                    if (el == 3) {
                        if (!frecv[S - c].empty()) {///daca gasesc al doilea membru al adunarii
                            afisare(liste[3].back().second, frecv[S - c].top());
                            return 0;
                        }
                        frecv[c].push(nrSecv - 1);
                    }
                }
            }
        }
        ++el;
    }

    for (int i = 0; i < liste[3].size(); ++i)
        for (int j = 0; j < liste[3].size(); ++j) {
            if (liste[3][i].first + liste[3][j].first == S) {
                afisare(liste[3][i].second, liste[3][j].second);
                return 0;
            }
        }

    fout << -1;///insemna ca nu exista
}

void afisare(int a, int b) {
    while (!m[a].empty()) {
        fout << m[a].top() << " ";
        m[a].pop();
    }

    while (!m[b].empty()) {
        fout << m[b].top() << " ";
        m[b].pop();
    }
}