Cod sursa(job #2675835)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 22 noiembrie 2020 17:25:57
Problema Loto Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>
#define NMAX 105
using namespace std;

/**************************************************/
/// INPUT / OUTPUT

ifstream f("loto.in");
ofstream g("loto.out");
/**************************************************/
/// GLOBAL DELCARATIONS

int n, target, foundSum = -1;
int sum, diff;
int arr[NMAX];

unordered_map <int, int> mapa;

vector < int > ans;
/**************************************************/
///-----------------------------------------------------------------
inline void ReadInput()
{
    f >> n >> target;
    for(int i = 1 ; i <= n ; ++ i) f >> arr[i];
}
///-----------------------------------------------------------------
inline void FindFirstSum()
{
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = i ; j <= n ; ++ j)
        {
            for(int k = j ; k <= n ; ++ k)
            {
                sum = arr[i] + arr[j] + arr[k];
                diff = target - sum;
                if(mapa[diff])
                {
                    foundSum = diff;
                    ans.push_back(arr[i]);
                    ans.push_back(arr[j]);
                    ans.push_back(arr[k]);
                    return;
                }
                else
                {
                    if(!mapa[sum]) mapa[sum] = 1;
                }
            }
        }
    }
}
///-----------------------------------------------------------------
inline void FindSecondSum()
{
    for(int i = 1 ; i <= n ; ++ i)
    {
        for(int j = i ; j <= n ; ++ j)
        {
            for(int k = j ; k <= n ; ++ k)
            {
                sum = arr[i] + arr[j] + arr[k];
                if(sum == foundSum)
                {
                    ans.push_back(arr[i]);
                    ans.push_back(arr[j]);
                    ans.push_back(arr[k]);
                    return;
                }
            }
        }
    }
}
///-----------------------------------------------------------------
inline void Solution()
{
    /// Foloseste un unordered map in loc de freq deoarece suma max e 600 mil :)

    /// get every sum possible
    FindFirstSum();
    if(foundSum == -1) return;
    /// find the sum that 'completes' the other half
    FindSecondSum();
}
///-----------------------------------------------------------------
inline void Output()
{
    if(foundSum == -1) g << "-1";
    for(auto it: ans) g << it << " ";
}
///-----------------------------------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}