Cod sursa(job #2623790)

Utilizator raluca1234Tudor Raluca raluca1234 Data 3 iunie 2020 20:32:35
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
// Infoarena - Loto
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

const int MAX_N = 1e2;

int arr[MAX_N];

struct sum_of_three{
    int a, b, c;
    int sum;
};

// sum_of_three sums[MAX_N * MAX_N * MAX_N];
std::vector <sum_of_three> sums;

int binarySearch(int sum)
{
    if (sum < 0) {
        return -1;
    }
    int left = 0;
    int right = sums.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (sums[mid].sum == sum) {
            return mid;
        }
        if (sums[mid].sum < sum) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

int main()
{
    std::ifstream fin("loto.in");
    std::ofstream fout("loto.out");

    int n, total_sum;
    fin >> n >> total_sum;
    
    for (int i = 0; i < n; ++i) {
        fin >> arr[i];
    }

    // int sums_size = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = j; k < n; ++k) {
                // sums[++sums_size] = {arr[i], arr[j], arr[k], arr[i] + arr[j] + arr[k]}; 
                sum_of_three current;
                current.a = arr[i];
                current.b = arr[j];
                current.c = arr[k];
                current.sum = arr[i] + arr[j] + arr[k];
                sums.emplace_back(current);
            }
        }
    }

    // Sortez sumele pentru a putea cauta binar dupa
    std::sort(sums.begin(), sums.end(),
        [](const sum_of_three& A, const sum_of_three& B) -> bool {
            return A.sum < B.sum;
        });

    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int k = j; k < n; ++k) {
                int position = binarySearch(total_sum - (arr[i] + arr[j] + arr[k]));
                if (position != -1) {
                    fout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << ' ' << 
                            sums[position].a << ' ' << sums[position].b << ' ' << sums[position].c << '\n';
                    return 0;
                }
            }
        }
    }
    fout << "-1\n";

    return 0;
}