Cod sursa(job #3359464)

Utilizator Belea_DariusBelea Mihai Darius Belea_Darius Data 28 iunie 2026 16:38:58
Problema Loto Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
//sortare francu + cb francu(teoretic mai rapide)
//poate nu destul si va trebui sa folosesc 2 pointers
#include <bits/stdc++.h>
#define MAXN 100

using namespace std;

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

int v[MAXN + 1];
struct elem{
    int x, y, z, s;
};
vector <elem> g;
vector <int> pi;


vector <elem> gen(int n){
    int i, j, k;
    vector <elem> rez;

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

void francu_qsort(int st, int dr){
    int b, e, pivot, aux;
    b = st;
    e = dr;
    pivot = g[pi[(b + e) / 2]].s;

    while(g[pi[b]].s < pivot){
        b++;
    }
    while(g[pi[e]].s > pivot){
        e--;
    }

    while(b < e){
        aux = pi[b];
        pi[b] = pi[e];
        pi[e] = aux;

        do{
            b++;
        }while(g[pi[b]].s < pivot);
        do{
            e--;
        }while(g[pi[e]].s > pivot);
    }

    if(st < e){
        francu_qsort(st, e);
    }
    if(e + 1 < dr){
        francu_qsort(e + 1, dr);
    }
}

int main()
{
    int n, suma, i, j, ok;
    elem aux;

    fin >> n >> suma;
    for(i = 1; i <= n; i++){
        fin >> v[i];
    }

    g = gen(n);
    pi.resize(g.size());

    for(i = 0; i < pi.size(); i++){
        pi[i] = i;
    }
    francu_qsort(0, pi.size() - 1);

//    for(i = 0; i < pi.size(); i++){
//        printf("%d ", g[pi[i]].s);
//    }

    i = ok = 0;
    j = pi.size() - 1;
    while(i < j && !ok){
        while(g[pi[i]].s + g[pi[j]].s > suma){
            j--;
        }
        if(g[pi[i]].s + g[pi[j]].s == suma){
            ok = 1;
        }
        i++;
    }
    i--;
    if(!ok){
        fout << "-1\n";
    }else{
        fout << g[pi[i]].x << " " << g[pi[i]].y << " " << g[pi[i]].z << " " << g[pi[j]].x << " " << g[pi[j]].y << " " << g[pi[j]].z << "\n";
    }
    return 0;
}