Cod sursa(job #2938014)

Utilizator vianistulTudor Vianu vianistul Data 11 noiembrie 2022 15:34:04
Problema Loto Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

using namespace std;

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

const int NMAX = 100;

int v[NMAX + 1];

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

vector <ceva> vals;


bool cmp(ceva a, ceva b){
    return a.sum < b.sum;
}

int main(){

    int n, s;
    fin >> n >> s;

    for(int i = 1; i <= n; i++)
        fin >> v[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++){
                vals.push_back({v[i] + v[j] + v[k], v[i], v[j], v[k]});
            }

    sort(vals.begin(), vals.end(), cmp);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++){
                int toFind = s - (v[i] + v[j] + v[k]);

                int last = 0;

                int st = 0, dr = (int)vals.size() - 1, ans = 0;
                while(st <= dr){
                    int mij = (st + dr);
                    if(vals[mij].sum <= toFind)
                        st = mij + 1, ans = mij;
                    else
                        dr = mij - 1;

                    assert(mij != last);
                    last = mij;
                }

                if(vals[ans].sum == toFind){
                    fout << v[i] << ' ' << v[j] << ' ' << v[k] << ' ' << vals[ans].a << ' ' << vals[ans].b << ' ' << vals[ans].c << '\n';
                    return 0;
                }
            }

    fout << -1 << '\n';

    return 0;
}