Cod sursa(job #3131914)

Utilizator dra_soloSolomon Dragos dra_solo Data 21 mai 2023 21:26:25
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;

const int MAX_N = 101;
const int MAX_MEM = MAX_N * MAX_N * MAX_N;
int numbers[MAX_MEM], num_numbers, target_sum, left_index[MAX_MEM], middle_index[MAX_MEM], right_index[MAX_MEM], node, comparisons[MAX_MEM];
map<int, int> order;

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

bool compare(int a, int b) {
    return numbers[a] < numbers[b];
}

int main() {
    fin >> num_numbers >> target_sum;
    node = num_numbers;
    int max_num = -1, min_num = 2e9;
    for (int i = 0; i < num_numbers; ++i) {
        fin >> numbers[i];
        min_num = min(min_num, numbers[i]);
        max_num = max(max_num, numbers[i]);
    }
    if (max_num * 6 < target_sum || min_num * 6 > target_sum) {
        fout << -1;
        return 0;
    }
    max_num = -1, min_num = 2e9;
    sort(numbers, numbers + num_numbers);
    fin.close();
    for (int i = 0; i < num_numbers; ++i) {
        for (int j = i; j < num_numbers; ++j) {
            for (int k = j; k < num_numbers; ++k) {
                comparisons[node - num_numbers] = node;
                numbers[node] = numbers[i] + numbers[j] + numbers[k];
                if (numbers[node] > target_sum) {
                    continue;
                }
                left_index[node] = i;
                middle_index[node] = j;
                right_index[node] = k;
                order.insert(make_pair(numbers[node], node));
                node++;
            }
        }
    }
    map<int, int>::iterator it;
    for (int i = 0; i < node - num_numbers; ++i) {
        int current_node = comparisons[i];
        it = order.find(target_sum - numbers[current_node]);
        if (it != order.end() && numbers[(*it).second] + numbers[current_node] == target_sum) {
            int solution_node = (*it).second;
            fout << numbers[left_index[current_node]] << " " << numbers[middle_index[current_node]] << " " << numbers[right_index[current_node]] << " " << numbers[left_index[solution_node]] << " " << numbers[middle_index[solution_node]] << " " << numbers[right_index[solution_node]];
            return 0;
        }
    }
    fout << -1;
}